Praktische Java-voorbeelden van de Big O-notatie

1. Overzicht

In deze tutorial zullen we praten over wat Big O Notation betekent. We zullen een paar voorbeelden doornemen om het effect ervan op de looptijd van uw code te onderzoeken.

2. De intuïtie van Big O-notatie

We horen vaak de prestaties van een algoritme beschreven met behulp van Big O Notation.

De studie van de prestaties van algoritmen - of algoritmische complexiteit - valt binnen het gebied van algoritme-analyse. Algoritme-analyse beantwoordt de vraag hoeveel bronnen, zoals schijfruimte of tijd, een algoritme verbruikt.

We zullen tijd beschouwen als een hulpmiddel. Hoe minder tijd een algoritme nodig heeft om te voltooien, hoe beter.

3. Constante-tijdalgoritmen - O (1)

Hoe beïnvloedt deze invoergrootte van een algoritme de looptijd? De sleutel tot het begrijpen van Big O is het begrijpen van de snelheden waarmee dingen kunnen groeien. Het tarief in kwestie is hier tijd genomen per invoergrootte.

Beschouw dit simpele stukje code:

int n = 1000; System.out.println ("Hey - je invoer is:" + n);

Het maakt duidelijk niet uit wat n is boven. Dit stuk code heeft een constante hoeveelheid tijd nodig om uit te voeren. Het is niet afhankelijk van de grootte van n.

Evenzo:

int n = 1000; System.out.println ("Hey - je invoer is:" + n); System.out.println ("Hmm .. ik doe meer dingen met:" + n); System.out.println ("En meer:" + n);

Het bovenstaande voorbeeld is ook een constante tijd. Zelfs als het 3 keer zo lang duurt om te rennen, is het hangt niet af van de grootte van de invoer, n. We duiden constante tijdalgoritmen als volgt aan: O (1). Let daar op O (2), O (3) of zelfs O (1000) zou hetzelfde betekenen.

Het maakt ons niet uit hoe lang het precies duurt om te rennen, alleen dat het constant tijd kost.

4. Logaritmische tijdalgoritmen - O (logboek n)

Constante-tijdalgoritmen zijn (asymptotisch) de snelste. Logaritmische tijd is de volgende snelste. Helaas zijn ze wat lastiger voor te stellen.

Een bekend voorbeeld van een logaritmisch tijdalgoritme is het binaire zoekalgoritme. Klik hier om te zien hoe u binair zoeken in Java implementeert.

Wat hier belangrijk is, is dat de looptijd groeit evenredig met de logaritme van de invoer (in dit geval loggen naar basis 2):

for (int i = 1; i <n; i = i * 2) {System.out.println ("Hey - ik ben bezig met kijken naar:" + i); }

Als n 8 is, is de uitvoer de volgende:

Hé - ik heb het druk met kijken naar: 1 Hé - ik heb het druk met kijken naar: 2 Hé - ik heb het druk met kijken naar: 4

Ons eenvoudige algoritme heeft log (8) = 3 keer uitgevoerd.

5. Lineaire tijdalgoritmen - Aan)

Na logaritmische tijdalgoritmen krijgen we de volgende snelste klasse: lineaire tijdalgoritmen.

Als we zeggen dat iets lineair groeit, bedoelen we dat het recht evenredig groeit met de grootte van de invoer.

Bedenk een simpele for-loop:

for (int i = 0; i <n; i ++) {System.out.println ("Hey - ik ben bezig met kijken naar:" + i); }

Hoe vaak wordt deze for-lus uitgevoerd? n keer natuurlijk! We weten niet precies hoe lang het duurt voordat dit wordt uitgevoerd - en daar maken we ons geen zorgen over.

Wat we wel weten, is dat het eenvoudige algoritme dat hierboven wordt gepresenteerd, lineair zal groeien met de grootte van de invoer.

We hebben liever een looptijd van 0.1n dan (1000n + 1000), maar beide zijn nog steeds lineaire algoritmen; ze groeien allebei direct in verhouding tot de omvang van hun input.

Nogmaals, als het algoritme is gewijzigd in het volgende:

for (int i = 0; i <n; i ++) {System.out.println ("Hey - ik ben bezig met kijken naar:" + i); System.out.println ("Hmm .. Laten we nog eens kijken naar:" + i); System.out.println ("En nog een:" + i); }

De looptijd zou nog steeds lineair zijn in de grootte van de invoer, n. We duiden lineaire algoritmen als volgt aan: Aan).

Net als bij de constante-tijdalgoritmen, geven we niet om de details van de runtime. O (2n + 1) is hetzelfde als Aan), aangezien Big O Notation zich bezighoudt met groei voor invoergroottes.

6. N Log N tijdalgoritmen - O (n log n)

n log n is de volgende klasse van algoritmen. De looptijd groeit evenredig met n log n van de input:

for (int i = 1; i <= n; i ++) {for (int j = 1; j <n; j = j * 2) {System.out.println ("Hey - ik ben bezig met kijken naar:" + i + "en" + j); }} 

Als het n is 8, dan wordt dit algoritme uitgevoerd 8 * logboek (8) = 8 * 3 = 24 keer. Of we strikte ongelijkheid hebben of niet in de for-lus, is niet relevant in het belang van een Big O-notatie.

7. Polynoom-tijdalgoritmen - O (np)

Vervolgens hebben we polynoom-tijdalgoritmen. Deze algoritmen zijn zelfs langzamer dan n log n algoritmen.

De term polynoom is een algemene term die kwadratisch bevat (n2), kubiek (n3), quartic (n4), enz. functies. Wat belangrijk is om te weten, is dat O (n2) is sneller dan O (n3) dat is sneller dan O (n4), enz.

Laten we eens kijken naar een eenvoudig voorbeeld van een kwadratisch tijdalgoritme:

for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {System.out.println ("Hey - ik ben bezig met kijken naar:" + i + "en" + j); }} 

Dit algoritme wordt uitgevoerd 82 = 64 keer. Merk op dat als we een andere for-lus zouden nesten, dit een O (n3) algoritme.

8. Exponentiële tijdalgoritmen - O(kn)

Nu komen we op gevaarlijk terrein; deze algoritmen groeien evenredig met een factor die wordt versterkt door de invoergrootte.

Bijvoorbeeld, O (2n) algoritmen verdubbelen met elke extra invoer. Dus als n = 2, deze algoritmen worden vier keer uitgevoerd; als n = 3, zullen ze acht keer worden uitgevoerd (een beetje zoals het tegenovergestelde van logaritmische tijdalgoritmen).

O (3n) algoritmen verdrievoudigen met elke extra invoer, O (kn) algoritmen worden k keer groter met elke extra invoer.

Laten we eens kijken naar een eenvoudig voorbeeld van een O (2n) tijd algoritme:

for (int i = 1; i <= Math.pow (2, n); i ++) {System.out.println ("Hey - ik ben bezig met kijken naar:" + i); }

Dit algoritme wordt uitgevoerd 28 = 256 keer.

9. Factoriële tijdalgoritmen - Aan!)

In de meeste gevallen is dit zo erg als het kan worden. Deze klasse van algoritmen heeft een looptijd die evenredig is met de faculteit van de invoergrootte.

Een klassiek voorbeeld hiervan is het oplossen van het handelsreizigersprobleem met een brute-force benadering om het op te lossen.

Een uitleg van de oplossing van het handelsreizigersprobleem valt buiten het bestek van dit artikel.

Laten we in plaats daarvan eens kijken naar een eenvoudig Aan!) algoritme, zoals in de vorige secties:

for (int i = 1; i <= factorial (n); i ++) {System.out.println ("Hey - ik ben bezig met kijken naar:" + i); }

waar faculteit (n) berekent eenvoudig n !. Als n 8 is, wordt dit algoritme uitgevoerd 8! = 40320 keer.

10. Asymptotische functies

Big O is wat bekend staat als een asymptotische functie. Dit alles betekent dat het zich bezighoudt met de prestaties van een algoritme op de limiet - d.w.z. - wanneer er veel invoer naar wordt gegooid.

Het maakt Big O niet uit hoe goed uw algoritme het doet met invoer van kleine omvang. Het houdt zich bezig met grote invoer (denk aan het sorteren van een lijst met een miljoen nummers versus het sorteren van een lijst met vijf nummers).

Een ander ding om op te merken is dat er zijn andere asymptotische functies. Big Θ (theta) en Big Ω (omega) beschrijven ook beide algoritmen op de limiet (onthoud, de grens dit betekent gewoon voor enorme inputs).

Om de verschillen tussen deze 3 belangrijke functies te begrijpen, moeten we eerst weten dat elk van Big O, Big Θ en Big Ω een set (d.w.z. een verzameling elementen).

Hier zijn de leden van onze sets zelf algoritmen:

  • Big O beschrijft de verzameling van alle algoritmen die worden uitgevoerd niet erger dan een bepaalde snelheid (het is een bovengrens)
  • Omgekeerd beschrijft Big Ω de verzameling van alle algoritmen die worden uitgevoerd niet beter dan een bepaalde snelheid (het is een ondergrens)
  • Ten slotte beschrijft Big Θ de verzameling van alle algoritmen die worden uitgevoerd Bij een bepaalde snelheid (het is als gelijkheid)

De definities die we hierboven hebben gegeven, zijn niet wiskundig nauwkeurig, maar ze zullen ons helpen begrijpen.

Meestal hoor je dingen die worden beschreven met Big O, maar het kan geen kwaad om te weten over Big Θ en Big Ω.

11. Conclusie

In dit artikel hebben we de Big O-notatie besproken en hoe het begrijpen van de complexiteit van een algoritme kan de looptijd van uw code beïnvloeden.

Een geweldige visualisatie van de verschillende complexiteitsklassen is hier te vinden.

Zoals gewoonlijk zijn de codefragmenten voor deze tutorial te vinden op GitHub.