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

Mentee

Člen

Mentee:4.10.2017 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.10.2017 19:32

Do something. If it does not work, do something else. Nothing is too crazy!

Neaktivní uživatel

Tvůrce

Neaktivní uživatel:4.10.2017 20:35

Konkretni priklad, ktery resis by pomohl.

Nahoru Odpovědět

4.10.2017 20:35

Neaktivní uživatelský účet

Mentee

Člen

Mentee:4.10.2017 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.10.2017 20:57

Do something. If it does not work, do something else. Nothing is too crazy!

pocitac770

Tvůrce

pocitac770:4.10.2017 21:06

No jistě, fiks, to mě mohlo napadnout

Nahoru Odpovědět

4.10.2017 21:06

pocitac770

Tvůrce

pocitac770:4.10.2017 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(n²), 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.10.2017 21:32

Mentee

Člen

Mentee:4.10.2017 21:45

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

Nahoru Odpovědět

4.10.2017 21:45

Do something. If it does not work, do something else. Nothing is too crazy!

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:4.10.2017 21:50

jestli dobre koukam, tak O(n⁵)

Nahoru Odpovědět

4.10.2017 21:50

https://www.facebook.com/peasantsandcastles/

Neaktivní uživatel

Tvůrce

Neaktivní uživatel:6.10.2017 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ý m² * n² 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

6.10.2017 9:56

Neaktivní uživatelský účet

Neaktivní uživatel

Tvůrce

Neaktivní uživatel:6.10.2017 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.10.2017 10:00

Neaktivní uživatelský účet

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:6.10.2017 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

6.10.2017 10:21

https://www.facebook.com/peasantsandcastles/

Neaktivní uživatel

Tvůrce

Neaktivní uživatel:6.10.2017 11:11

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

Nahoru Odpovědět

6.10.2017 11:11

Neaktivní uživatelský účet

Mentee

Člen

Mentee:10.10.2017 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.10.2017 18:06

Nahoru Odpovědět

10.10.2017 18:05

Do something. If it does not work, do something else. Nothing is too crazy!

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:10.10.2017 18:14

V tomhle pripade ne.

Jinak Convert uvnitr vola int.Parse()

Nahoru Odpovědět

10.10.2017 18:14

https://www.facebook.com/peasantsandcastles/

Marian Benčat

Člen

Marian Benčat:10.10.2017 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

10.10.2017 21:29

Totalitní admini..

Honza Bittner

Tvůrce

Honza Bittner:10.10.2017 21:42

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

Nahoru Odpovědět

10.10.2017 21:42

FIT ČVUT alumnus :-) Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/tenhobi/ama.

Marian Benčat

Člen

Marian Benčat:10.10.2017 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í nⁿ rychlejší, než n² :-)

Nahoru Odpovědět

10.10.2017 21:44

Totalitní admini..

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:10.10.2017 21:54

jen při nízkých n

Nahoru Odpovědět

10.10.2017 21:54

https://www.facebook.com/peasantsandcastles/

Marian Benčat

Člen

Marian Benčat:10.10.2017 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.10.2017 22:04

Nahoru Odpovědět

10.10.2017 22:03

Totalitní admini..

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:10.10.2017 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.10.2017 22:11

https://www.facebook.com/peasantsandcastles/

Marian Benčat

Člen

Marian Benčat:10.10.2017 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.10.2017 22:17

Totalitní admini..

Marian Benčat

Člen

Marian Benčat:10.10.2017 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.10.2017 22:21

Totalitní admini..

Marian Benčat

Člen

Marian Benčat:10.10.2017 22:23

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

Nahoru Odpovědět

10.10.2017 22:23

Totalitní admini..

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:10.10.2017 22:37

Jenze kdyz mas neefektivni algoritmus, treba n² 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

10.10.2017 22:37

https://www.facebook.com/peasantsandcastles/

Marian Benčat

Člen

Marian Benčat:10.10.2017 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

10.10.2017 22:49

Totalitní admini..

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:10.10.2017 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.10.2017 22:58

https://www.facebook.com/peasantsandcastles/

Marian Benčat

Člen

Marian Benčat:10.10.2017 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

10.10.2017 23:05

Totalitní admini..

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:10.10.2017 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.10.2017 23:10

https://www.facebook.com/peasantsandcastles/

Marian Benčat

Člen

Marian Benčat:10.10.2017 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

10.10.2017 23:14

Totalitní admini..

Honza Bittner

Tvůrce

Honza Bittner:10.10.2017 23:35

Tak to jsem zvědav. :-)

Nahoru Odpovědět

10.10.2017 23:35

FIT ČVUT alumnus :-) Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/tenhobi/ama.

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:11.10.2017 10:22

cekam

Nahoru Odpovědět

11.10.2017 10:22

https://www.facebook.com/peasantsandcastles/

Lukáš Hruda

Tvůrce

Lukáš Hruda:12.10.2017 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 nⁿ 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(n²), 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(n²), 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

12.10.2017 9:56

Marian Benčat

Člen

Marian Benčat:12.10.2017 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

12.10.2017 10:35

Totalitní admini..

Marian Benčat

Člen

Marian Benčat:12.10.2017 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.10.2017 10:35

Totalitní admini..

hanpari

Člen

hanpari:12.10.2017 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

12.10.2017 11:01

Marian Benčat

Člen

Marian Benčat:12.10.2017 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

12.10.2017 11:21

Totalitní admini..

hanpari

Člen

hanpari:12.10.2017 11:56

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

Nahoru Odpovědět

12.10.2017 11:56

Honza Bittner

Tvůrce

Honza Bittner:12.10.2017 12:17

Já chápu, že když budeš mít algoritmus, kde když třeba O(n⁵) pracuje s cache a ten s O(n²) přistupuje na disk, tak je pravědpodobnost, že bude ten O(n⁵) 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

12.10.2017 12:17

FIT ČVUT alumnus :-) Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/tenhobi/ama.

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:12.10.2017 12:26

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

Editováno 12.10.2017 12:28

Nahoru Odpovědět

12.10.2017 12:26

https://www.facebook.com/peasantsandcastles/

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:12.10.2017 12:31

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

Nahoru Odpovědět

12.10.2017 12:31

https://www.facebook.com/peasantsandcastles/

Lukáš Hruda

Tvůrce

Lukáš Hruda:12.10.2017 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í k2n², 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 = 10¹⁰⁰, 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

12.10.2017 12:35

Nejčastěji vyhledáváné

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