Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Avatar
Mentee
Člen
Avatar
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!
Avatar
Odpovídá na Mentee
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
Avatar
Mentee
Člen
Avatar
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!
Avatar
pocitac770
Tvůrce
Avatar
pocitac770:4.10.2017 21:06

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

 
Nahoru Odpovědět
4.10.2017 21:06
Avatar
pocitac770
Tvůrce
Avatar
Odpovídá na Mentee
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(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.10.2017 21:32
Avatar
Mentee
Člen
Avatar
Odpovídá na pocitac770
Mentee:4.10.2017 21:45

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

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

jestli dobre koukam, tak O(n5)

Nahoru Odpovědět
4.10.2017 21:50
https://www.facebook.com/peasantsandcastles/
Avatar
Odpovídá na Luboš Běhounek Satik
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ý 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
6.10.2017 9:56
Neaktivní uživatelský účet
Avatar
Odpovídá na Neaktivní uživatel
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
Avatar
Odpovídá na Neaktivní uživatel
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/
Avatar
Odpovídá na Luboš Běhounek Satik
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
Avatar
Mentee
Člen
Avatar
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!
Avatar
Odpovídá na Mentee
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/
Avatar
Odpovídá na Mentee
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..
Avatar
Honza Bittner
Tvůrce
Avatar
Odpovídá na Marian Benčat
Honza Bittner:10.10.2017 21:42

No, zpracovávat data při n * log(n) vs n666 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.
Avatar
Odpovídá na Honza Bittner
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í nn rychlejší, než n2 :-)

Nahoru Odpovědět
10.10.2017 21:44
Totalitní admini..
Avatar
Odpovídá na Marian Benčat
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/
Avatar
Odpovídá na Luboš Běhounek Satik
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..
Avatar
Odpovídá na Marian Benčat
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/
Avatar
Odpovídá na Luboš Běhounek Satik
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..
Avatar
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..
Avatar
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..
Avatar
Odpovídá na Marian Benčat
Luboš Běhounek Satik:10.10.2017 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
10.10.2017 22:37
https://www.facebook.com/peasantsandcastles/
Avatar
Odpovídá na Luboš Běhounek Satik
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..
Avatar
Odpovídá na Marian Benčat
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/
Avatar
Odpovídá na Luboš Běhounek Satik
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..
Avatar
Odpovídá na Marian Benčat
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/
Avatar
Odpovídá na Luboš Běhounek Satik
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..
Avatar
Honza Bittner
Tvůrce
Avatar
Odpovídá na Marian Benčat
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.
Avatar
Nahoru Odpovědět
11.10.2017 10:22
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Marian Benčat
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 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
12.10.2017 9:56
Avatar
Odpovídá na Lukáš Hruda
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..
Avatar
Odpovídá na Marian Benčat
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..
Avatar
hanpari
Tvůrce
Avatar
Odpovídá na Marian Benčat
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
Avatar
Odpovídá na hanpari
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..
Avatar
hanpari
Tvůrce
Avatar
Odpovídá na Marian Benčat
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
Avatar
Honza Bittner
Tvůrce
Avatar
Odpovídá na Marian Benčat
Honza Bittner:12.10.2017 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
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.
Avatar
Odpovídá na Marian Benčat
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/
Avatar
Odpovídá na Honza Bittner
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/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Marian Benčat
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í 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
12.10.2017 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.