Praktické príklady Java veľkej notácie

1. Prehľad

V tomto návode si povieme čo Veľká O notácia znamená. Prejdeme si niekoľko príkladov, aby sme preskúmali jeho vplyv na prevádzkovú dobu vášho kódu.

2. Intuícia veľkej O notácie

Často počujeme výkon algoritmu opísaného pomocou Big O Notation.

Štúdium výkonnosti algoritmov - alebo algoritmickej zložitosti - spadá do oblasti analýzy algoritmov. Analýza algoritmov odpovedá na otázku, koľko zdrojov, ako napríklad miesto na disku alebo čas, algoritmus spotrebuje.

Budeme sa pozerať na čas ako na zdroj. Zvyčajne platí, že čím kratší čas potrebný na dokončenie algoritmu, tým lepšie.

3. Algoritmy konštantného času - O (1)

Ako táto veľkosť vstupu algoritmu ovplyvňuje jeho čas chodu? Kľúčom k pochopeniu Big O je porozumenie rýchlosti, akou môžu veci rásť. Príslušná sadzba je čas potrebný na veľkosť vstupu.

Zvážte tento jednoduchý kúsok kódu:

int n = 1 000; System.out.println ("Hej - váš vstup je:" + n);

Je zrejmé, že nezáleží na tom, čo n je vyššie. Táto časť kódu trvá konštantne dlho. Nie je to závislé od veľkosti n.

Podobne:

int n = 1 000; System.out.println ("Hej - váš vstup je:" + n); System.out.println ("Hmm .. robím viac vecí s:" + n); System.out.println ("A ďalšie:" + n);

Vyššie uvedený príklad je tiež konštantný čas. Aj keď jej spustenie trvá 3x dlhšie, je to nezávisí od veľkosti vstupu, n. Algoritmy konštantného času označujeme nasledovne: O (1). Poznač si to O (2), O (3) alebo dokonca O (1 000) by znamenalo to isté.

Nezaujíma nás presne, ako dlho to trvá, iba to, že to trvá neustále.

4. Logaritmické časové algoritmy - O (log n)

Algoritmy konštantného času sú (asymptoticky) najrýchlejšie. Logaritmický čas je ďalší najrýchlejší. Bohužiaľ, je to o niečo zložitejšie si predstaviť.

Jedným z bežných príkladov algoritmu logaritmického času je algoritmus binárneho vyhľadávania. Ak chcete zistiť, ako implementovať binárne vyhľadávanie v prostredí Java, kliknite sem.

Tu je dôležité, aby doba chodu rastie úmerne s logaritmom vstupu (v tomto prípade sa prihláste do bázy 2):

for (int i = 1; i <n; i = i * 2) {System.out.println ("Hej - hľadám zaneprázdnene:" + i); }

Ak n je 8, výstup bude nasledujúci:

Hej - som zaneprázdnený pozeraním: 1 Hej - mám zaneprázdnený pozeraním: 2 Hej - mám zaneprázdnený pozeraním: 4

Náš jednoduchý algoritmus spustil protokol (8) = 3-krát.

5. Lineárne časové algoritmy - O (n)

Po logaritmických časových algoritmoch dostaneme ďalšiu najrýchlejšiu triedu: lineárne časové algoritmy.

Ak hovoríme, že niečo rastie lineárne, máme na mysli to, že rastie priamo úmerne veľkosti jeho vstupov.

Vymyslite jednoduchý cyklus for:

for (int i = 0; i <n; i ++) {System.out.println ("Hej - zaneprázdnený som sledovaním:" + i); }

Koľkokrát to funguje pre slučku? n krát, samozrejme! Nevieme presne, ako dlho to bude trvať, a s tým si nerobíme starosti.

Vieme však, že jednoduchý algoritmus uvedený vyššie bude lineárne narastať s veľkosťou jeho vstupu.

Dali by sme prednosť dobehu 0,1 n než (1 000 n + 1 000), ale oba sú stále lineárnymi algoritmami; obe rastú priamo úmerne s veľkosťou ich vstupov.

Opäť platí, že ak bol algoritmus zmenený na nasledujúci:

for (int i = 0; i <n; i ++) {System.out.println ("Hej - zaneprázdnený som sledovaním:" + i); System.out.println ("Hmm .. Poďme sa ešte pozrieť na:" + i); System.out.println ("A ďalšie:" + i); }

Runtime by bol stále lineárny vo veľkosti svojho vstupu, n. Lineárne algoritmy označujeme nasledovne: O (n).

Rovnako ako pri algoritmoch s konštantným časom, ani my sa nestaráme o špecifiká runtime. O (2 n + 1) je to isté ako O (n), keďže Big O Notation sa zaoberá rastom veľkosti vstupov.

6. Algoritmy času N Log N - O (n log n)

n prihlásiť n je ďalšou triedou algoritmov. Prevádzková doba rastie úmerne s n prihlásiť n vstupu:

for (int i = 1; i <= n; i ++) {for (int j = 1; j <n; j = j * 2) {System.out.println ("Hey - I am busy looking at:" + i + "a" + j); }} 

Napríklad ak n je 8, potom sa tento algoritmus spustí 8 * denník (8) = 8 * 3 = 24 krát. To, či máme v cykle for prísnu nerovnosť alebo nie, je z dôvodu veľkej O notácie irelevantné.

7. Polynomiálne časové algoritmy - O (np)

Ďalej máme polynomiálne časové algoritmy. Tieto algoritmy sú ešte pomalšie ako n prihlásiť n algoritmy.

Pojem polynóm je všeobecný pojem, ktorý obsahuje kvadratické (n2), kubický (n3), kvartálne (n4), atď. Je dôležité vedieť to O (n2) je rýchlejší ako O (n3) ktorý je rýchlejší ako O (n4), atď.

Pozrime sa na jednoduchý príklad kvadratického časového algoritmu:

for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {System.out.println ("Hej - hľadám zaneprázdnene:" + i + "a" + j); }} 

Tento algoritmus sa spustí 82 = 64 krát. Všimnite si, že ak by sme vnorili ďalší cyklus for, stalo by sa z neho O (n3) algoritmus.

8. Exponenciálne časové algoritmy - O (kn)

Teraz sa dostávame na nebezpečné územie; tieto algoritmy rastú úmerne k niektorému faktoru umocňovanému veľkosťou vstupu.

Napríklad, O (2n) algoritmy sa zdvojnásobujú s každým ďalším vstupom. Takže ak n = 2, tieto algoritmy pobežia štyrikrát; ak n = 3, budú bežať osemkrát (niečo ako opak logaritmických časových algoritmov).

O (3n) algoritmy sa strojnásobia s každým ďalším vstupom, O (kn) algoritmy budú s každým ďalším vstupom kkrát väčšie.

Pozrime sa na jednoduchý príklad súboru O (2n) časový algoritmus:

for (int i = 1; i <= Math.pow (2, n); i ++) {System.out.println ("Hej - hľadám zaneprázdnene na:" + i); }

Tento algoritmus sa spustí 28 = 256 krát.

9. Faktoriálne časové algoritmy - O (n!)

Vo väčšine prípadov je to dosť zlé, ako to bude možné. Táto trieda algoritmov má dobu chodu úmernú faktoriálu veľkosti vstupu.

Klasickým príkladom je riešenie problému obchodného cestujúceho pomocou riešenia hrubou silou.

Vysvetlenie riešenia problému cestujúcich v predaji je nad rámec tohto článku.

Namiesto toho sa pozrime na jednoduchý O (n!) algoritmus, ako v predchádzajúcich častiach:

for (int i = 1; i <= faktoriál (n); i ++) {System.out.println ("Hej - zaneprázdnený som sledovaním:" + i); }

kde faktoriál (n) jednoducho počíta n !. Ak n je 8, tento algoritmus sa spustí 8! = 40320 krát.

10. Asymptotické funkcie

Veľké O je známe ako asymptotická funkcia. To všetko znamená, že sa týka výkonu algoritmu na hranici - tj. - keď je na to hodené veľa vstupu.

Big O sa nestará o to, ako dobre je váš algoritmus so vstupmi malej veľkosti. Týka sa to veľkých vstupov (zvážte triedenie zoznamu s miliónom čísel oproti triedeniu zoznamu s 5 číslami).

Ďalšia vec, ktorú je potrebné poznamenať, je, že existujú aj ďalšie asymptotické funkcie. Big Θ (theta) a Big Ω (omega) tiež popisuje algoritmy na limite (pamätajte, limit to znamená len pre obrovské vstupy).

Aby sme pochopili rozdiely medzi týmito 3 dôležitými funkciami, najskôr musíme vedieť, že každá z funkcií Big O, Big Θ a Big Ω popisuje nastaviť (t.j. zbierka prvkov).

Tu sú členmi našich množín samotné algoritmy:

  • Big O popisuje množinu všetkých spustených algoritmov o nič horšie než určitá rýchlosť (je to horná hranica)
  • Naopak, Big Ω popisuje množinu všetkých spustených algoritmov o nič lepšie než určitá rýchlosť (je to dolná hranica)
  • Nakoniec Big Θ popisuje množinu všetkých spustených algoritmov o určitá rýchlosť (je to ako rovnosť)

Definície, ktoré sme uviedli vyššie, nie sú matematicky presné, ale pomôžu nášmu pochopeniu.

Zvyčajne budete počuť veci opísané pomocou funkcie Big O, ale nezaškodí vedieť o Big Θ a Big Ω.

11. Záver

V tomto článku sme sa zaoberali notáciou Big O a ako Pochopenie zložitosti algoritmu môže ovplyvniť prevádzkovú dobu vášho kódu.

Skvelú vizualizáciu rôznych tried zložitosti nájdete tu.

Útržky kódu pre tento tutoriál ako obvykle nájdete na GitHub.


$config[zx-auto] not found$config[zx-overlay] not found