Robil som samoštúdium na Big-O. Chápem, ako dať algoritmom tieto príklady:
O (N):
for(int i = 0; i < n; i++)
sum++;
O (N ^ 2):
for(int i = 0; i < n; i++)
for( int j = 0; j < n; j++)
sum++;
O (N ^ 3):
for(int i = 0; i < n; i++)
for( int j = 0; j < n * n; j++)
sum++;
Narazil som na tieto zápisy, ktorým úplne nerozumiem. Ako ich uvádzam z hľadiska algoritmov?
Možno by som to mal povedať takto: napíš algoritmus, ktorý zaberá čas v pomere k:
- O ((n ^ 3) / 4)
- log n ^ 3
- O ((log ^ 2) n) + O (n)
- 4 ^ n
- n ^ 3/2
odpovede:
9 pre odpoveď č. 1Obávam sa, že ste nepochopili zápis „Big-O“.
Zápis nie je „vyjadrený“ ako algoritmus. Skôr notácia Big-O popisuje vlastnosť algoritmu.
Takže to nie je „O (N), možno vyjadriť ako XXX“, ale skôr „algoritmus XXX má zložitosť O (N)“.
To znamená, že je celkom rozumné požiadať o príklady algoritmov s určitou zložitosťou; niektoré už máte. Ak chcete odpovedať na svoje otázky:
O (4 ^ n) je rovnaké ako O (e ^ n), často písané ako O (exp (n)) (skúste pochopiť, prečo je rovnaké). O (4 ^ n) patrí do triedy algoritmov s „exponenciálnou zložitosťou“ (EXPTIME). Mnoho dôležitých problémov v matematike / CS má exponenciálnu zložitosť (alebo takmer exponenciálnu zložitosť).
Algoritmus s exponenciálnou zložitosťou by bol napríklad naivným riešením diskrétny logaritmický problém.
Pokiaľ ide o ďalšie zložitosti, nemôžem uviesť príklad, pravdepodobne ho však nájdete tak, že sa trochu googlujete.
-1 pre odpoveď č. 2
Algoritmy, ktoré ste uviedli, sú prísnenehovoriac o Big-O, ale o Thete. Big-O je asymptotická horná hranica, čo znamená, že na horšom prípade vstupu bude doba spustenia rovnaká, ale nie je „t“ pre všetky vstupy, kde ako Theta je úzka väzba, čo znamená, že prevádzková doba bude vždy taká. inštancia triediaceho algoritmu, ktorý má už zadaný zoznam ako vstup, alebo vyhľadávací algoritmus, kde je potrebné nájsť veci, ktoré sa majú nájsť, prvým prvkom v zozname (v tomto prípade sa porovnáva binárne vyhľadávanie s lineárnym vyhľadávaním).