Přidej si svou IT školu do profilu a najdi spolužáky zde na síti :)

Diskuze: Jak spočítat asymptotickou složitost?

Ostatní jazyky Ostatní programovací jazyky Jak spočítat asymptotickou složitost?

Aktivity (1)
Avatar
Mentee
Člen
Avatar
Mentee:4. října 19:32

Ahoj,
mám odhadnout asymptotickou složitost. Už mám přečtených pár návodů jak na to, ale stále mi není úplně jasné, jak mám složitost spočítat pokud mám 4 vstupy na kterých závisí složitost.
V návodech psali, že mám zanedbat multiplikativní a aditivní konstanty, co to znamená?

Odpovědět 4. října 19:32
Do something. If it does not work, do something else. Nothing is too crazy!
Avatar
Taskkill
Šéfredaktor
Avatar
Odpovídá na Mentee
Taskkill:4. října 20:35

Konkretni priklad, ktery resis by pomohl.

 
Nahoru Odpovědět 4. října 20:35
Avatar
Mentee
Člen
Avatar
Mentee:4. října 20:57

Potřebuji spočítat složitost tohoto kódu, pomůžete mi prosím?

static void Main(string[] args)
        {
            //zpracovavani inputu:
            string input = Console.ReadLine();
            string[] arrInput = new string[4];
            arrInput = input.Split(' ');

            int n=int.Parse(arrInput[0]);
            int m=int.Parse(arrInput[1]);
            int a=int.Parse(arrInput[2]);
            int b=int.Parse(arrInput[3]);
            int res = 0;
            bool[,] plan = new bool[n, m];
for (int y = 0; y < m; y++)
 {
                for (int x = 0; x < n; x++)
                {

                        for (int i = 0; i < n; i++)
                    {
                        for (int ii = 0; ii < m; ii++)
                        {
                            plan[i, ii] = true;
                        }
                    }
                    if (x+a<=n)
                    {
                        for (int i = x; i < x + a; i++)
                        {
                            plan[i, y] = false;
                        }
                        for (int y2 = 0; y2 < m; y2++)
                        {
                            for (int x2 = 0; x2 < n; x2++)
                            {
                                if(x2+b<=n)
                                {
                                    bool empty = true
                                    for (int i = x2; i < x2 + b; i++)
                                    {
                                        if(plan[i,y2]==false)
                                        {
                                            empty = false;
                                            break;
                                        }
                                    }
                                    if(empty==true)
                                    {
                                        res+=2
                                        }
                                }
                                if (y2 + b <= m)
                                {
                                    bool empty = true;
                                    for (int i = y2; i < y2 + b; i++)
                                    {
                                        if (plan[x2, i] == false)
                                        {
                                            empty = false;
                                            break;
                                        }
                                    }
                                    if (empty == true)
                                    {
                                        res+=2;
                                    }
                                }

                            }
                        }
                    }
                    else
                    {
                        break;
                    }

                }
            }
            if (a == b)
            {
                res /= 2;
            }
            if (a == 1 || b == 1)
            {
                res /= 2;
            }
            Console.WriteLine(res);
            Console.ReadKey(false);
        }
    }
Nahoru Odpovědět 4. října 20:57
Do something. If it does not work, do something else. Nothing is too crazy!
Avatar
pocitac770
Redaktor
Avatar
pocitac770:4. října 21:06

No jistě, fiks, to mě mohlo napadnout :D

 
Nahoru Odpovědět 4. října 21:06
Avatar
pocitac770
Redaktor
Avatar
Odpovídá na Mentee
pocitac770:4. října 21:32

Nechci podvádět, tak si tvůj kód nebudu číst, ale pokud se nepletu, tak pokud jsi nevytvořil nějakou extrémní prasárnu, tak by příklad měl mít řešení se slozitostí O(n2), dle mého názoru.... Jen aby ostatní neříkali že sem píšu bez vážného zájmu pomoci :)

 
Nahoru Odpovědět 4. října 21:32
Avatar
Mentee
Člen
Avatar
Odpovídá na pocitac770
Mentee:4. října 21:45

Dobře, ale jak jsi došel k tomu n2 ?

Nahoru Odpovědět 4. října 21:45
Do something. If it does not work, do something else. Nothing is too crazy!
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na pocitac770
Luboš Satik Běhounek:4. října 21:50

jestli dobre koukam, tak O(n5)

Nahoru Odpovědět  +4 4. října 21:50
https://www.facebook.com/peasantsandcastles/
Avatar
Taskkill
Šéfredaktor
Avatar
Odpovídá na Luboš Satik Běhounek
Taskkill:6. října 9:56

A není to odhad hodně shora? Kdybys to popisoval konkrétně, neměl bys zohlednit to, že to má základ nějaký m2 * n2 a pak uvnitř nějaký to [n + (n+1)] / 2
V několika různých případech.
Jen se ptám.

 
Nahoru Odpovědět  +1 6. října 9:56
Avatar
Taskkill
Šéfredaktor
Avatar
Odpovídá na Taskkill
Taskkill:6. října 10:00

Teď mě cvaklo, že vycházíš z nejhoršího možného případů, kdy budou m a n stejně velká čísla. Ok

 
Nahoru Odpovědět 6. října 10:00
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na Taskkill
Luboš Satik Běhounek:6. října 10:21

Nějaký /2 tady neřešíš, viz zadání:

V návodech psali, že mám zanedbat multiplikativní a aditivní konstanty, co to znamená?

To znamená, že třeba n+n nebo n+1 nebo n/2 je pořád n

Jinak ano, je to maximální časová náročnost toho algoritmu

Nahoru Odpovědět  +2 6. října 10:21
https://www.facebook.com/peasantsandcastles/
Avatar
Taskkill
Šéfredaktor
Avatar
Odpovídá na Luboš Satik Běhounek
Taskkill:6. října 11:11

Jo, to je pravda. To jsem si nepřečetl.

 
Nahoru Odpovědět 6. října 11:11
Avatar
Mentee
Člen
Avatar
Mentee:10. října 18:05

Díky za odpovědi.
Mohli byste mi prosím ještě trochu pomoci?
Jaký je rozdíl mezi metodami:

int i = int.Parse(s);

int i = Convert.ToInt32(s);

Mohu změnou těchto metod vylepšit složitost?

Editováno 10. října 18:06
Nahoru Odpovědět 10. října 18:05
Do something. If it does not work, do something else. Nothing is too crazy!
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na Mentee
Luboš Satik Běhounek:10. října 18:14

V tomhle pripade ne.

Jinak Convert uvnitr vola int.Parse()

Nahoru Odpovědět 10. října 18:14
https://www.facebook.com/peasantsandcastles/
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na Mentee
Marian Benčat:10. října 21:29

Takovéto věci neřeš.. stejně v budoucnu zjistíš, že asymptotická složitost je v reálném světě informace vesměs úplně totálně k ničemu. Jakákoliv složitost kódu je v reálném světě úplně k ničemu ;-)

Nahoru Odpovědět  -1 10. října 21:29
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
Honza Bittner
Šupák
Avatar
Odpovídá na Marian Benčat
Honza Bittner:10. října 21:42

No, zpracovávat data při n * log(n) vs n666 je IMHO docela rozdíl. ;)

Nahoru Odpovědět  +1 10. října 21:42
Milovník Dartu. Student FIT ČVUT. Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/...
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na Honza Bittner
Marian Benčat:10. října 21:44

No, tak ano.. toto je rozdíl... a těžko se to bude hledat jinde..

Ale je naprosto běžné, že kód, který nevolá ani žádnou metodu, jen prostě tupé cykly a přiřazování bude se složitostí nn rychlejší, než n2 :-)

Nahoru Odpovědět 10. října 21:44
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na Marian Benčat
Luboš Satik Běhounek:10. října 21:54

jen při nízkých n :)

Nahoru Odpovědět 10. října 21:54
https://www.facebook.com/peasantsandcastles/
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na Luboš Satik Běhounek
Marian Benčat:10. října 22:03

I při vysokých. Samozřejmě to bude mít svoji mez. Ale již při nějakým normálním příkladu..

Když napíši defakto úplně totálně STEJNÝ kód, který dělá ty samé instrukce, tak jeden může být bezproblému několika set násobně rychlejší i pro malé N.

CPU není vůbec to, co něco brzdí a je to už hodně dávno zcela irelevantní veličina (počet operací) a s tím z velké části je irelevantní většinou i asymptotická náročnost.

Editováno 10. října 22:04
Nahoru Odpovědět 10. října 22:03
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na Marian Benčat
Luboš Satik Běhounek:10. října 22:11

To záleží hodně na tom, co zpracováváš, v práci běžně zpracováváme několik jednotek až desítek GB dat a tam ta složitost znamená že běh aplikace netrvá několik minut, ale několik hodin, když použiješ nevhodnej algoritmus :) .

Nahoru Odpovědět 10. října 22:11
https://www.facebook.com/peasantsandcastles/
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na Luboš Satik Běhounek
Marian Benčat:10. října 22:17

Prave ty by si měl vědět nejlépe, že na tom jak data v paměti naalokujes,.nebo jak je máš v paměti u sebe vzhledem k algoritmu, ti udělá na tom samém kódu z 1sec,.vteřin 50.

Nahoru Odpovědět 10. října 22:17
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
Marian Benčat
Redaktor
Avatar
Marian Benčat:10. října 22:21

Jeden super primitivní případ..jsem překvapený, že i takoví blbouni jako tvurci androidu si toto uvědomuji:
https://android-developers.googleblog.com/…riented.html?m=1

Nahoru Odpovědět 10. října 22:21
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
Marian Benčat
Redaktor
Avatar
Marian Benčat:10. října 22:23

Proto, pokud chceš psát skutečně výkonný kód, tak nepises podle OOP .

Nahoru Odpovědět 10. října 22:23
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na Marian Benčat
Luboš Satik Běhounek:10. října 22:37

Jenze kdyz mas neefektivni algoritmus, treba n2 misto n, tak ten ti nevytezuje vic jen procesor, ale prave i treba tu pamet / jiny zdroje.

A priklad v odkazu je idealni pripad, casto jsou ty vypocty o nekolik radu slozitejsi, tam pak ten rozdil nebude tak velkej.

A pokud chces hnat vykon opravdu na kost, tak ano, OOP ma nejakou rezii navic, to pak uz zalezi na konkretnim algoritmu a implementaci, ta ztrata muze bejt nekolik desitek procent v krajnim pripade a nemeritelna v druhym extremu.

Nahoru Odpovědět  +1 10. října 22:37
https://www.facebook.com/peasantsandcastles/
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na Luboš Satik Běhounek
Marian Benčat:10. října 22:49

Nepochopil jsi mě správně. Ale jsem moc rad, ze si zminil ten priklad s gigabyty dat... To je totiz priklad, kde se ti data se kterymi musis pracovat nevejdou do pameti RAM, je to tedy stejny pripad jakp cache miss... Ty tedy musis pouzivat tzv. Externi algoritmy.. Treba pro razeni je to external merge sort.. Kdyz mas takoveto algorotmy, tak pro tebe bude vesmes vzdy mnohem rychlejsi algoritmus, ktery ma n na ntou, ale na disk saha jen jednou, nez algoritmus s n na 2, ktery musi sahat na disk kazdych par prvku pole, protoze se mu nevejdou do pameti.. A ted si nahrad v tom mem tvrzeni HDD a RAM za RAM a CPU Cache a mas to same.. Jen se to projevi narozdil od tvych GB dat temer u kazdeho SW .

Nahoru Odpovědět  +1 10. října 22:49
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na Marian Benčat
Luboš Satik Běhounek:10. října 22:58

Ono se nam ty data do RAM v pohode vejdou, nikdy je nemas v pameti najednou vsechny a jsou to algoritmy, kdy se ty data cely nactou a pak se s nima delaj nejaky slozitejsi vypocty, takze tohle resit nemusime.

Jak jsi to teda myslel? Ja te pochopil tak, ze podle tebe tolik nezalezi na asymptoticky slozitosti algoritmu, protoze procesor ma vykon dostatecny a brzdi to napr. ta operacni pamet... :)

Nahoru Odpovědět 10. října 22:58
https://www.facebook.com/peasantsandcastles/
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na Luboš Satik Běhounek
Marian Benčat:10. října 23:05

Ano presne tak jsem to myslel. Nejvetsi chybu co muze programator udelat, je optimalizovat beh kodu podle asymptoticke slozitosti.. Kupodivu to byva casto naopak, vetsinou udelas upravu, ktera zvedne asymptotickou slozitost (casto i o ten rad), program ale bude rychlejsi.

Nahoru Odpovědět  -1 10. října 23:05
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na Marian Benčat
Luboš Satik Běhounek:10. října 23:10

S tim nesouhlasim a presne o tom jsem i psal vejs, ze kdyz zvednes asymptotickou slozitost behu toho algoritmu, tak tim v programu zvednes i mnozstvi pristupu do pameti -> rychlejsi to rozhodne nebude, protoze mas vic prace jak pro procesor, tak i radove vic pristupu do ty pameti, co te brzdi.

Nahoru Odpovědět 10. října 23:10
https://www.facebook.com/peasantsandcastles/
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na Luboš Satik Běhounek
Marian Benčat:10. října 23:14

napis mi prosim zitra az budu u pc a ja te presvedcim zdrojakem, ktery si sam u sebe pustis. klidne ti to dam v cpp

Nahoru Odpovědět  +1 10. října 23:14
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
Honza Bittner
Šupák
Avatar
Odpovídá na Marian Benčat
Honza Bittner:10. října 23:35

Tak to jsem zvědav. :-)

Nahoru Odpovědět  +2 10. října 23:35
Milovník Dartu. Student FIT ČVUT. Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/...
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Nahoru Odpovědět 11. října 10:22
https://www.facebook.com/peasantsandcastles/
Avatar
Odpovídá na Marian Benčat
Lukáš Hruda (Luckin):12. října 9:56

Kdyz mas takoveto algorotmy, tak pro tebe bude vesmes vzdy mnohem rychlejsi algoritmus, ktery ma n na ntou, ale na disk saha jen jednou, nez algoritmus s n na 2, ktery musi sahat na disk kazdych par prvku pole, protoze se mu nevejdou do pameti.

Tohle je nesmysl. Pokud pracuješ s daty řádově v GB, tzn. n je v řádu miliard, pak nn je tak astronomicky obrovské číslo, že žádný procesor na světě tolik operací nezpracuje v rozumném čase, tedy pokud za rozumný čas nepovažujeme miliony let. Jakýkoliv algoritmus se složitostí O(n2), i kdyby v každém kroku prováděl 100 přístupů na disk, bude mnohonásobně rychlejší.

Algoritmy s vyšší asymptotickou časovou složitostí se mohou vyplatit tehdy, kdy n je velmi malé. Například budeme-li chtít seřadit 10 číselných hodnot, pak bude výhodnější použít insert sort, se složitostí O(n2), než quick sort, se složitostí O(n log(n)), protože pro tak malý počet operací režie quick sortu převáží vysokou složitost jednoduchého insert sortu. Pokud ale zvedeme n na řekněme 1000, pak už quick sort bude několika násobně rychlejší. A co teprve pro n = 1 000 000 či n = 1 000 000 000.

 
Nahoru Odpovědět  +4 12. října 9:56
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Marian Benčat:12. října 10:35

To není pravda.. a kdybych nebyl líný si najít na disku C:\\ těch potřebných 3GB místo, abych si mohl do VS přidat tooling pro vývoj pro C++ (ach jo VS :-( ) , tak už vám to dávno dokáži. Takto to musíte vydržet do víkendu ;-)

Nahoru Odpovědět  -1 12. října 10:35
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na Marian Benčat
Marian Benčat:12. října 10:35

Mohl bych to ukázat i na C#, ale nechci, aby se mi do toho pletla VM a GC, aby jste se nemohli vymluvit ;-)

Nahoru Odpovědět 12. října 10:35
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
hanpari
Redaktor
Avatar
Odpovídá na Marian Benčat
hanpari:12. října 11:01

Jsem sice naprosto skeptický k tomu, co tvrdíš, ale docela by mne zajímalo, jak a co hodláš demonstrovat. Možná bude lepší, když to tu napíšeš, než se pustíš do nějakých testů.

 
Nahoru Odpovědět  +1 12. října 11:01
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na hanpari
Marian Benčat:12. října 11:21

Budu demonstrovat to, že algoritmus s větší asymptotickou složitostí bude vždy mnohonásobně rychlejší, pro libovolně velké N.

Nahoru Odpovědět  -1 12. října 11:21
In Smalltalk, everything is an object, In Clojure, everything is a list, In Javascript, everything is fucking mistake
Avatar
hanpari
Redaktor
Avatar
Odpovídá na Marian Benčat
hanpari:12. října 11:56

V tom pripade jsi zraly na Nobelovku. Nechces to preformulovat?

 
Nahoru Odpovědět  +3 12. října 11:56
Avatar
Honza Bittner
Šupák
Avatar
Odpovídá na Marian Benčat
Honza Bittner:12. října 12:17

Já chápu, že když budeš mít algoritmus, kde když třeba O(n5) pracuje s cache a ten s O(n2) přistupuje na disk, tak je pravědpodobnost, že bude ten O(n5) rychlejší, ale obecně, pokud využívají stejné prostředky tak si nemyslím, že by prostě, už z podstaty věci, mohl být rychlejší.

Nahoru Odpovědět  +1 12. října 12:17
Milovník Dartu. Student FIT ČVUT. Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/...
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na Marian Benčat
Luboš Satik Běhounek:12. října 12:26

Klidne to posli v C#, nemyslim si, ze by byl ten pes zakopanej v VM nebo GC.

Editováno 12. října 12:28
Nahoru Odpovědět 12. října 12:26
https://www.facebook.com/peasantsandcastles/
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na Honza Bittner
Luboš Satik Běhounek:12. října 12:31

Od urcityho N bude vzdycky ten asymptoticky jednodussi algoritmus rychlejsi, jen to N muze bejt treba vyssi.

Nahoru Odpovědět  +1 12. října 12:31
https://www.facebook.com/peasantsandcastles/
Avatar
Odpovídá na Marian Benčat
Lukáš Hruda (Luckin):12. října 12:35

To, co píšeš, je nesmysl z principu věci. Je to i matematicky dokázané, ale jelikož ten důkaz není tak jednoduchý abych ho zde z hlavy sepsal, tak jen ve stručnosti:
Existuje důvod, proč se v asymptotických složitostech ignorují multiplikativní a aditivní konstanty. Je to proto, že když jsou dvě funkce, např f1(n) a f2(n), a jedna znich roste rychleji, např f1, pak, ať f2(n) vynásobíš libovolně vysokou konstantou k, stejně vždy bude existovat nějaké n0, pro které platí, že pro všechna n > n0 bude f1(n) vyšší než než f2(n).
Například máme-li algoritmus se složitostí k1n a druhý se složitostí k2n2, kde k2 je velmi malé a k1 naopak velmi velké, bude pravda, že pro relativně malé hodnoty n bude algoritmus s kvadratickou složitostí rychlejší. Může to být pro n = 1000 nebo pro n = 1 000 000 000, může to být i pro n = 10100, ale vždy bude možné nalézt dostatečně vysoké n pro které bude ten kvadratický algoritmus už pomalejší, i když může být třeba i velmi vysoké.
A teď si představ, že k1 může reprezentovat například ten čas potřebný k přístupu na disk a k2 čas potřebný k přístupu do cpu cache. Je jedno jak velký časový rozdíl mezi těmito dvěma časy je, ale vždy bude možné vytvořit takové množství dat, aby ten kvadratický algoritmus byl pomalejší.

 
Nahoru Odpovědět  +1 12. října 12:35
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 40 zpráv z 40.