Praktični Java primjeri oznake Big O

1. Pregled

U ovom uputstvu razgovarat ćemo o čemu Oznaka Big O znači. Proći ćemo kroz nekoliko primjera kako bismo istražili njegov učinak na vrijeme rada vašeg koda.

2. Intuicija velikog O zapisa

Često čujemo izvedba algoritma opisanog pomoću Big O Notacije.

Proučavanje izvedbe algoritama - ili algoritamske složenosti - spada u područje analize algoritama. Analiza algoritma daje odgovor na pitanje koliko resursa, poput prostora na disku ili vremena, algoritam troši.

Vreme ćemo gledati kao na resurs. Tipično, što manje vremena algoritmu treba za dovršenje, to bolje.

3. Algoritmi konstantnog vremena - O (1)

Kako ova ulazna veličina algoritma utječe na njegovo vrijeme izvođenja? Ključ razumijevanja Big Oa je razumijevanje brzina kojima stvari mogu rasti. Ovdje je stopa u pitanju vrijeme potrebno za ulaznu veličinu.

Razmislite o ovom jednostavnom dijelu koda:

int n = 1000; System.out.println ("Hej - vaš unos je:" + n);

Jasno je da nije važno što n je, gore. Za izvršavanje ovog dijela koda potrebno je stalno vrijeme. Ne ovisi o veličini n.

Slično:

int n = 1000; System.out.println ("Hej - vaš unos je:" + n); System.out.println ("Hmm .. Radim još stvari s:" + n); System.out.println ("I više:" + n);

Gornji primjer je također konstantno vrijeme. Čak i ako traje 3 puta više vremena, treba ne ovisi o veličini unosa, n. Algoritme s konstantnim vremenom označavamo na sljedeći način: O (1). Imajte na umu da O (2), O (3) ili čak O (1000) značilo bi isto.

Ne zanima nas koliko točno vremena treba trčati, samo da treba stalno vrijeme.

4. Logaritamski algoritmi vremena - O (zapisnik n)

Algoritmi s konstantnim vremenom su (asimptotski) najbrži. Logaritamsko vrijeme je sljedeće najbrže. Nažalost, malo su nezgodnije zamisliti.

Jedan od uobičajenih primjera logaritamskog vremenskog algoritma je binarni algoritam pretraživanja. Da biste vidjeli kako implementirati binarno pretraživanje na Javi, kliknite ovdje.

Ovdje je važno da vrijeme rada raste proporcionalno logaritmu ulaza (u ovom slučaju, prijavite se na bazu 2):

for (int i = 1; i <n; i = i * 2) {System.out.println ("Hej - zauzet sam gledajući:" + i); }

Ako n je 8, izlaz će biti sljedeći:

Hej - zauzet sam gledanjem: 1 Hej - zauzet sam gledanjem: 2 Hej - zauzet sam gledanjem: 4

Naš jednostavni algoritam pokrenuo je log (8) = 3 puta.

5. Linearni vremenski algoritmi - Na)

Nakon logaritamskih vremenskih algoritama dobivamo sljedeću najbržu klasu: algoritmi linearnog vremena.

Ako kažemo da nešto raste linearno, mislimo da raste izravno proporcionalno veličini svojih ulaza.

Zamislite jednostavnu petlju for:

for (int i = 0; i <n; i ++) {System.out.println ("Hej - zauzet sam gledajući:" + i); }

Koliko puta ovo radi za petlju? n puta, naravno! Ne znamo točno koliko će vremena trebati da ovo traje - i zbog toga se ne brinemo.

Ono što znamo je da će gore predstavljeni jednostavni algoritam rasti linearno s veličinom unosa.

Više bismo voljeli vrijeme izvođenja od 0,1n od (1000n + 1000), ali oba su još uvijek linearni algoritmi; oboje rastu izravno proporcionalno veličini uloženih sredstava.

Opet, ako je algoritam promijenjen u sljedeće:

for (int i = 0; i <n; i ++) {System.out.println ("Hej - zauzet sam gledajući:" + i); System.out.println ("Hm .. Pogledajmo još jedanput:" + i); System.out.println ("I još jedno:" + i); }

Vrijeme izvođenja i dalje bi bilo linearno u veličini unosa, n. Linearne algoritme označavamo na sljedeći način: Na).

Kao i kod algoritama s konstantnim vremenom, i nas nije briga za specifičnosti vremena izvođenja. O (2n + 1) je isto što i Na), jer se Big O Notation bavi rastom ulaznih veličina.

6. N Log N vremenski algoritmi - O (n zapisnik n)

n log n je sljedeća klasa algoritama. Vrijeme rada raste proporcionalno s n log n unosa:

for (int i = 1; i <= n; i ++) {for (int j = 1; j <n; j = j * 2) {System.out.println ("Hej - zauzet sam gledanjem:" + i + "i" + j); }} 

Na primjer, ako je n je 8, tada će se pokrenuti ovaj algoritam 8 * zapisnik (8) = 8 * 3 = 24 puta. Bez obzira imamo li strogu nejednakost ili ne u for petlji, nebitno je zbog velike O bilješke.

7. Polinomski vremenski algoritmi - O (np)

Dalje imamo polinomne vremenske algoritme. Ti su algoritmi još sporiji od n log n algoritmi.

Pojam polinom je opći pojam koji sadrži kvadrat (n2), kubični (n3), kvartični (n4)itd. funkcije. Ono što je važno znati je to O (n2) je brži od O (n3) što je brže od O (n4)itd.

Pogledajmo jednostavan primjer algoritma kvadratnog vremena:

for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {System.out.println ("Hej - zauzet sam gledanjem:" + i + "i" + j); }} 

Ovaj algoritam će se pokrenuti 82 = 64 puta. Napomena, ako bismo ugnijezdili drugu for petlju, ovo bi postalo O (n3) algoritam.

8. Eksponencijalni vremenski algoritmi - O (kn)

Sad ulazimo na opasan teritorij; ti algoritmi rastu proporcionalno nekom faktoru potenciranom ulaznom veličinom.

Na primjer, O (2n) algoritmi se udvostručuju sa svakim dodatnim ulazom. Pa ako n = 2, ovi će se algoritmi izvoditi četiri puta; ako n = 3, oni će se izvoditi osam puta (nekako poput suprotnosti logaritamskim algoritmima vremena).

O (3n) algoritmi se utrostruče sa svakim dodatnim ulazom, O (kn) algoritmi će postati k puta veći sa svakim dodatnim unosom.

Pogledajmo jednostavan primjer O (2n) algoritam vremena:

for (int i = 1; i <= Math.pow (2, n); i ++) {System.out.println ("Hej - zauzet sam gledajući:" + i); }

Ovaj algoritam će se pokrenuti 28 = 256 puta.

9. Faktorijski vremenski algoritmi - Na!)

U većini slučajeva ovo je prilično loše koliko i dobiti. Ova klasa algoritama ima vrijeme izvođenja proporcionalno faktorijelu veličine ulaza.

Klasičan primjer toga je rješavanje problema trgovačkog putnika korištenjem grube sile da bi se to riješilo.

Objašnjenje rješenja problema putničkog trgovca izvan je dosega ovog članka.

Umjesto toga, pogledajmo jednostavan Na!) algoritam, kao u prethodnim odjeljcima:

for (int i = 1; i <= factorial (n); i ++) {System.out.println ("Hej - zauzet sam gledajući:" + i); }

gdje faktorijel (n) jednostavno izračunava n !. Ako je n 8, pokrenut će se ovaj algoritam 8! = 40320 puta.

10. Asimptotske funkcije

Veliko O je ono što je poznato kao asimptotska funkcija. Sve to znači da se tiče izvedbe algoritma na granici - tj. - kad se na njega baci puno unosa.

Big O-a nije briga koliko dobro funkcionira vaš algoritam s ulazima male veličine. Radi se o velikim ulazima (razmislite o sortiranju popisa od milijun brojeva u odnosu na sortiranju popisa od 5 brojeva).

Još jedna stvar koju treba napomenuti je to postoje i druge asimptotske funkcije. Big Θ (theta) i Big Ω (omega) također opisuju algoritme na granici (sjetite se, ograničenje to samo znači za ogromne ulaze).

Da bismo razumjeli razlike između ove 3 važne funkcije, prvo moramo znati da svaka od velikih O, velikih Θ i velikih Ω opisuje postavljen (tj. zbirka elemenata).

Ovdje su članovi naših skupova sami algoritmi:

  • Big O opisuje skup svih algoritama koji se izvode ni gore od određene brzine (to je gornja granica)
  • Suprotno tome, Veliki Ω opisuje skup svih algoritama koji se izvode nije bolje od određene brzine (to je donja granica)
  • Napokon, Big Θ opisuje skup svih pokrenutih algoritama na određena brzina (to je poput jednakosti)

Definicije koje smo gore naveli nisu matematički točne, ali će nam pomoći u razumijevanju.

Obično ćete čuti stvari opisane pomoću Big O-a, ali ne škodi znati o Big Θ i Big Ω.

11. Zaključak

U ovom smo članku razgovarali o zapisu Big O i kako razumijevanje složenosti algoritma može utjecati na vrijeme rada vašeg koda.

Sjajnu vizualizaciju različitih složenosti možete pronaći ovdje.

Kao i obično, isječci koda za ovu lekciju možete pronaći na GitHubu.