Grote O, hoe bereken/benader je het?

De meeste mensen met een graad in CS zullen zeker weten waar Grote O staat.
Het helpt ons te meten hoe goed een algoritme schaalt.

Maar ik ben benieuwd, hoe berekent of schat u de complexiteit van uw algoritmen u?

---

Antwoord 1, autoriteit 100%

Ik zal mijn best doen om het hier in eenvoudige bewoordingen uit te leggen, maar wees gewaarschuwd dat mijn studenten een paar maanden nodig hebben om dit onderwerp te begrijpen. U kunt meer informatie vinden in hoofdstuk 2 van de Datastructuren en -algoritmen in Javaboek.

---

Er is geen mechanische proceduredie kan worden gebruikt om de BigOh te krijgen.

Als een “kookboek”, om de BigOhte verkrijgen uit een stukje code dat je eerst nodig hebt om te beseffen dat je een wiskundige formule aan het maken bent om te tellen hoeveel stappen van berekeningen worden uitgevoerd met een invoer van enige omvang.

Het doel is simpel: algoritmen vergelijken vanuit een theoretisch oogpunt, zonder de noodzaak om de code uit te voeren. Hoe minder stappen, hoe sneller het algoritme.

Stel bijvoorbeeld dat je dit stukje code hebt:

int sum(int* data, int N) {
    int result = 0;               // 1
    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }
    return result;                // 4
}

Deze functie retourneert de som van alle elementen van de array, en we willen een formule maken om de computationele complexiteitvan die functie:

Number_Of_Steps = f(N)

We hebben dus f(N), een functie om het aantal rekenstappen te tellen. De invoer van de functie is de grootte van de te verwerken structuur. Het betekent dat deze functie wordt aangeroepen als:

Number_Of_Steps = f(data.length)

De parameter nneemt de waarde data.lengthaan. Nu hebben we de daadwerkelijke definitie van de functie f()nodig. Dit gebeurt vanuit de broncode, waarin elke interessante regel is genummerd van 1 tot 4.

Er zijn veel manieren om de BigOh te berekenen. Vanaf dit punt gaan we ervan uit dat elke zin die niet afhankelijk is van de grootte van de invoergegevens een constant C-getal rekenstappen neemt.

We gaan het individuele aantal stappen van de functie toevoegen, en noch de declaratie van de lokale variabele, noch de return-instructie hangt af van de grootte van de data-array.

Dat betekent dat regel 1 en 4 elk C aantal stappen nemen, en de functie is ongeveer als volgt:

f(N) = C + ??? + C

Het volgende deel is het definiëren van de waarde van het forstatement. Onthoud dat we het aantal rekenstappen tellen, wat betekent dat de hoofdtekst van de for-instructie nkeer wordt uitgevoerd. Dat is hetzelfde als C, nkeer toevoegen:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

Er is geen mechanische regel om te tellen hoe vaak de hoofdtekst van de forwordt uitgevoerd, je moet het tellen door te kijken naar wat de code doet. Om de berekeningen te vereenvoudigen, negeren we de variabele initialisatie, voorwaarde en incrementele delen van de for-instructie.

Om de werkelijke BigOh te krijgen, hebben we de Asymptotische analysevan de functie nodig. Dit gaat ongeveer zo:

1. Haal alle constanten Cweg.
2. Van f()haal het polynomiumin zijn standard form.
3. Verdeel de termen van het polynomium en sorteer ze op de groeisnelheid.
4. Behoud degene die groter wordt wanneer ninfinitynadert.

Onze f()heeft twee termen:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Alle Cconstanten en overbodige delen wegnemen:

f(N) = 1 + N ^ 1

Aangezien de laatste term degene is die groter wordt wanneer f()oneindig nadert (denk aan limieten) dit is het BigOh-argument en de functie sum()heeft een BigOh van:

O(N)

---

Er zijn een paar trucjes om lastige trucs op te lossen: gebruik optellingenwanneer je maar kunt.

Deze code kan bijvoorbeeld eenvoudig worden opgelost met sommaties:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

Het eerste dat gevraagd moet worden, is de volgorde van uitvoering van foo(). Hoewel het gebruikelijk is om O(1)te zijn, moet je dit aan je professoren vragen. O(1)betekent (bijna, meestal) constante C, onafhankelijk van de grootte n.

De for-instructie op zin nummer één is lastig. Terwijl de index eindigt op 2 * N, wordt de verhoging met twee gedaan. Dat betekent dat de eerste foralleen nstappen wordt uitgevoerd, en dat we de telling door twee moeten delen.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

De zin nummer tweeis nog lastiger omdat het afhangt van de waarde van i. Kijk eens: de index i neemt de waarden: 0, 2, 4, 6, 8, …, 2 * N, en de tweede forwordt uitgevoerd: N keer de eerste, N – 2 de tweede, N – 4 de derde… tot aan de N / 2 stage, waarop de tweede fornooit wordt uitgevoerd.

In formule betekent dat:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

Nogmaals, we tellen het aantal stappen. En per definitie moet elke sommatie altijd bij één beginnen en eindigen bij een getal groter of gelijk aan één.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(We gaan ervan uit dat foo()O(1)is en Cstappen neemt.)

We hebben hier een probleem: wanneer ide waarde N / 2 + 1naar boven neemt, eindigt de binnenste Sommatie op een negatief getal! Dat is onmogelijk en fout. We moeten de sommatie in tweeën splitsen, wat het cruciale punt is op het moment dat iN / 2 + 1neemt.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

Sinds het cruciale moment i > N / 2, de innerlijke forwordt niet uitgevoerd en we gaan uit van een constante C-uitvoeringscomplexiteit op zijn lichaam.

Nu kunnen de sommaties worden vereenvoudigd met behulp van enkele identiteitsregels:

1. Samentelling(w van 1 tot N)( C ) = N * C
2. Optelling (w van 1 tot N)( A (+/-) B ) = Sommatie (w van 1 tot N)( A ) (+/-) Sommatie (w van 1 tot N)( B )
3. Optelling(w van 1 tot N)( w * C ) = C * Sommatie(w van 1 tot N)( w ) (C is een constante, onafhankelijk van w)
4. Samentelling (w van 1 tot N)( w ) = (N * (N + 1)) / 2

Een beetje algebra toepassen:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )
f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )
=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )
=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 
   (N / 2 - 1) * (N / 2) / 2 = 
   ((N ^ 2 / 4) - (N / 2)) / 2 = 
   (N ^ 2 / 8) - (N / 4)
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )
f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + C * N
f(N) = C * 1/4 * N ^ 2 + C * N

En de BigOh is:

O(N?)

---

Antwoord 2, autoriteit 14%

Grote O geeft de bovengrens voor tijdcomplexiteit van een algoritme. Het wordt meestal gebruikt in combinatie met het verwerken van datasets (lijsten), maar kan ook elders worden gebruikt.

Een paar voorbeelden van hoe het wordt gebruikt in C-code.

Stel dat we een array van n elementen hebben

int array[n];

Als we toegang wilden tot het eerste element van de array, zou dit O(1) zijn, omdat het niet uitmaakt hoe groot de array is, het duurt altijd dezelfde constante tijd om het eerste item te krijgen.

x = array[0];

Als we een nummer in de lijst wilden vinden:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

Dit zou O(n) zijn, omdat we hoogstens de hele lijst zouden moeten doorzoeken om ons nummer te vinden. De Big-O is nog steeds O(n), ook al vinden we ons nummer misschien de eerste keer dat we door de lus lopen, omdat Big-O de bovengrens voor een algoritme beschrijft (omega is voor ondergrens en theta is voor strakke grens) .

Als we bij geneste lussen komen:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

Dit is O(n^2), aangezien we voor elke passage van de buitenste lus ( O(n)) de hele lijst opnieuw moeten doorlopen, zodat de n’s vermenigvuldigen, zodat we n kwadraat krijgen.

Dit komt nauwelijks aan de oppervlakte, maar wanneer je complexere algoritmen gaat analyseren, komt complexe wiskunde met bewijzen in het spel. Ik hoop dat dit je in ieder geval vertrouwd maakt met de basis.

---

Antwoord 3, autoriteit 7%

Hoewel het nuttig is om te weten hoe u de Big O-tijd voor uw specifieke probleem kunt bepalen, kan het kennen van enkele algemene gevallen u een heel eind helpen bij het nemen van beslissingen in uw algoritme.

Hier zijn enkele van de meest voorkomende gevallen, overgenomen van http://en.wikipedia.org /wiki/Big_O_notation#Orders_of_common_functions:

O(1) – Bepalen of een getal even of oneven is; een opzoektabel of hashtabel met constante grootte gebruiken

O(logn) – Een item in een gesorteerde array zoeken met een binaire zoekopdracht

O(n) – Een item vinden in een ongesorteerde lijst; twee n-cijferige getallen toevoegen

O(n²) – Twee n-cijferige getallen vermenigvuldigen met een eenvoudig algoritme; het toevoegen van twee n?n matrices; bellen sorteren of invoegen sorteren

O(n³) – Twee n?n matrices vermenigvuldigen met een eenvoudig algoritme

O(cⁿ) – Het vinden van de (exacte) oplossing voor het handelsreizigersprobleem met behulp van dynamisch programmeren; bepalen of twee logische uitspraken equivalent zijn met brute kracht

O(n!) – Het probleem van de handelsreiziger oplossen via brute-force search

O(nⁿ) – Vaak gebruikt in plaats van O(n!) om eenvoudiger formules voor asymptotische complexiteit af te leiden

---

Antwoord 4, autoriteit 3%

Kleine herinnering: de big O-notatie wordt gebruikt om asymptotischecomplexiteit aan te duiden (dat wil zeggen, wanneer de omvang van het probleem tot oneindig groeit), enhet verbergt een constante.

Dit betekent dat tussen een algoritme in O(n) en één in O(n²), de snelste niet altijd de eerste is (hoewel er altijd een waarde van n bestaat zodat voor problemen van grootte >n, het eerste algoritme is het snelst).

Merk op dat de verborgen constante erg afhangt van de implementatie!

In sommige gevallen is de runtime ook geen deterministische functie van de grootten van de invoer. Neem bijvoorbeeld het sorteren met snel sorteren: de tijd die nodig is om een ​​array van n elementen te sorteren is geen constante, maar hangt af van de beginconfiguratie van de array.

Er zijn verschillende tijdscomplexiteiten:

• Slechtste geval (meestal het eenvoudigst te achterhalen, maar niet altijd erg zinvol)

• Gemiddeld geval (meestal veel moeilijker te achterhalen…)

• …

Een goede introductie is An Introduction to the Analysis of Algorithmsdoor R. Sedgewick en P. Flajolet.

Zoals je zegt, premature optimisation is the root of all evil, en (indien mogelijk) zou profileringecht altijd moeten worden gebruikt bij het optimaliseren van code. Het kan u zelfs helpen de complexiteit van uw algoritmen te bepalen.

---

Antwoord 5, autoriteit 2%

Als ik de antwoorden hier zie, denk ik dat we kunnen concluderen dat de meesten van ons inderdaad de volgorde van het algoritme benaderen door er naarnaar te kijken en gezond verstand te gebruiken in plaats van het te berekenen met bijvoorbeeld de mastermethodezoals we op de universiteit dachten.
Dat gezegd hebbende, moet ik eraan toevoegen dat zelfs de professor ons (later) aanmoedigde om er echt over te nadenkenin plaats van het alleen maar te berekenen.

Ik zou ook willen toevoegen hoe het wordt gedaan voor recursieve functies:

stel dat we een functie hebben zoals (schemacode):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

die recursief de faculteit van het gegeven getal berekent.

De eerste stap is om te proberen het prestatiekenmerk te bepalen voor alleen de hoofdtekst van de functiein dit geval wordt er niets speciaals gedaan in de hoofdtekst, alleen een vermenigvuldiging (of de terugkeer van de waarde 1).

Dus de prestatie voor het lichaam is: O(1)(constant).

Probeer dit vervolgens te bepalen voor het aantal recursieve aanroepen. In dit geval hebben we n-1 recursieve oproepen.

Dus de prestatie voor de recursieve aanroepen is: O(n-1)(de volgorde is n, aangezien we de onbeduidende delen weggooien).

Voeg die twee dan samen en je hebt dan de uitvoering voor de hele recursieve functie:

1 * (n-1) = O(n)

---

Peter, om uw problemen;de methode die ik hier beschrijf, behandelt dit eigenlijk heel goed. Maar houd er rekening mee dat dit nog steeds een benaderingis en geen volledig wiskundig correct antwoord. De hier beschreven methode is ook een van de methoden die we op de universiteit hebben geleerd, en als ik me goed herinner, werd deze gebruikt voor veel geavanceerdere algoritmen dan de faculteit die ik in dit voorbeeld gebruikte.
Het hangt natuurlijk allemaal af van hoe goed je de looptijd van de body van de functie en het aantal recursieve aanroepen kunt inschatten, maar dat geldt net zo goed voor de andere methoden.

---

Antwoord 6, autoriteit 2%

Als uw kosten een polynoom zijn, houdt u gewoon de term van de hoogste orde, zonder de vermenigvuldigingsfactor. Bijv.:

O((n/2 + 1)*(n/2)) = O(n²/4 + n/2) = O(n²/4) = O(n²)

Dit werkt niet voor oneindige series, let wel. Er is niet één recept voor het algemene geval, hoewel voor sommige veelvoorkomende gevallen de volgende ongelijkheden van toepassing zijn:

O(log N) < O(N) < O(Nlog N) < O(N²) < O(N^k) < O(eⁿ) < O(n!)

---

Antwoord 7, autoriteit 2%

Ik denk erover na in termen van informatie. Elk probleem bestaat uit het leren van een bepaald aantal bits.

Uw basishulpmiddel is het concept van beslissingspunten en hun entropie. De entropie van een beslispunt is de gemiddelde informatie die het je zal geven. Als een programma bijvoorbeeld een beslissingspunt met twee vertakkingen bevat, is de entropie de som van de kans op elke vertakking maal de log₂van de inverse waarschijnlijkheid van die vertakking. Dat is hoeveel je leert door die beslissing uit te voeren.

Bijvoorbeeld, een if-statement met twee takken, beide even waarschijnlijk, heeft een entropie van 1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1. Dus de entropie is 1 bit.

Stel dat u zoekt in een tabel met N items, zoals N=1024. Dat is een 10-bits probleem omdat log(1024) = 10 bits. Dus als je het kunt doorzoeken met IF-statements die even waarschijnlijke uitkomsten hebben, zou het 10 beslissingen moeten nemen.

Dat krijg je met binair zoeken.

Stel dat u lineair zoekt. Je kijkt naar het eerste element en vraagt ​​of het degene is die je wilt. De kansen zijn 1/1024 dat het zo is, en 1023/1024 dat het niet zo is. De entropie van die beslissing is 1/1024*log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * ongeveer 0 = ongeveer 0,01 bit. Je hebt heel weinig geleerd! De tweede beslissing is niet veel beter. Daarom is lineair zoeken zo traag. In feite is het exponentieel in het aantal bits dat je moet leren.

Stel dat u aan het indexeren bent. Stel dat de tabel is voorgesorteerd in een groot aantal bakken, en u gebruikt enkele van alle bits in de sleutel om rechtstreeks naar het tabelitem te indexeren. Als er 1024 bins zijn, is de entropie 1/1024 * log (1024) + 1/1024 * log (1024) + … voor alle 1024 mogelijke uitkomsten. Dit is 1/1024 * 10 keer 1024 uitkomsten, of 10 bits entropie voor die ene indexeringsoperatie. Daarom is het indexeren van zoekopdrachten snel.

Denk nu aan sorteren. Je hebt N items en je hebt een lijst. Voor elk item moet u zoeken naar waar het item in de lijst terechtkomt en het vervolgens aan de lijst toevoegen. Het sorteren kost dus ongeveer N keer het aantal stappen van de onderliggende zoekopdracht.

Dus sorteringen op basis van binaire beslissingen met ongeveer even waarschijnlijke uitkomsten, nemen allemaal ongeveer O(N log N) stappen. Een O(N)-sorteeralgoritme is mogelijk als het gebaseerd is op indexering.

Ik heb ontdekt dat bijna alle algoritmische prestatieproblemen op deze manier kunnen worden bekeken.

---

Antwoord 8

Laten we bij het begin beginnen.

Accepteer allereerst het principe dat bepaalde eenvoudige bewerkingen op gegevens kunnen worden uitgevoerd in O(1)tijd, dat wil zeggen in tijd die onafhankelijk is van de grootte van de invoer. Deze primitieve bewerkingen in C bestaan ​​uit

1. Rekenkundige bewerkingen (bijv. + of %).
2. Logische bewerkingen (bijv. &&).
3. Vergelijkingsbewerkingen (bijv. <=).
4. Structuurtoegangsbewerkingen (bijv. array-indexering zoals A[i], of pointer-fol-
   laag met de -> operator).
5. Eenvoudige toewijzing, zoals het kopiëren van een waarde naar een variabele.
6. Oproepen naar bibliotheekfuncties (bijv. scanf, printf).

De rechtvaardiging voor dit principe vereist een gedetailleerde studie van de machine-instructies (primitieve stappen) van een typische computer. Elk van de beschreven bewerkingen kan worden uitgevoerd met een klein aantal machine-instructies; vaak zijn er maar één of twee instructies nodig.
Als gevolg hiervan kunnen verschillende soorten statements in C worden uitgevoerd in O(1)tijd, dat wil zeggen in een constante hoeveelheid tijd onafhankelijk van invoer. Deze eenvoudige omvatten

1. Toewijzingsinstructies die geen functieaanroepen in hun expressies bevatten.
2. Lees uitspraken.
3. Schrijf instructies die geen functieaanroepen nodig hebben om argumenten te evalueren.
4. De jump-instructies break, continue, goto en return-expressie, waarbij
   expressie bevat geen functieaanroep.

In C worden veel for-loops gevormd door een indexvariabele te initialiseren tot een bepaalde waarde en
die variabele elke keer rond de lus met 1 verhogen. De for-lus eindigt wanneer
de index bereikt een limiet. Bijvoorbeeld de for-loop

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

gebruikt indexvariabele i. Het verhoogt i met 1 elke keer rond de lus, en de iteraties
stop wanneer ik n bereikt? 1.

Concentreer u echter voorlopig op de eenvoudige vorm van for-loop, waarbij het verschil tussen de uiteindelijke en initiële waarden, gedeeld door de hoeveelheid waarmee de indexvariabele wordt verhoogd, ons vertelt hoe vaak we gaan rond de lus. Die telling is exact, tenzij er manieren zijn om de lus te verlaten via een jump-instructie; het is sowieso een bovengrens voor het aantal iteraties.

Bijvoorbeeld, de for-lus herhaalt ((n ? 1) ? 0)/1 = n ? 1 times,
aangezien 0 de beginwaarde is van i, n ? 1 is de hoogste waarde die wordt bereikt door i (d.w.z. wanneer i
bereikt n?1, de lus stopt en er vindt geen iteratie plaats met i = n?1), en 1 wordt opgeteld
naar i bij elke iteratie van de lus.

In het eenvoudigste geval, waarbij de tijd die in de loop-body wordt doorgebracht voor elk hetzelfde is
iteratie, we kunnen de big-oh bovengrens voor het lichaam vermenigvuldigen met het aantal
keer rond de lus. Strikt genomen moeten we dan O(1) tijd toevoegen om te initialiseren
de lusindex en O(1) tijd voor de eerste vergelijking van de lusindex met de
limiet, omdat we één keer meer testen dan dat we de cirkel rondgaan. Echter, tenzij
het is mogelijk om de lus nul keer uit te voeren, de tijd om de lus te initialiseren en te testen
de limiet eenmaal is een term van lage orde die kan worden verwijderd door de sommatieregel.

---

Beschouw nu dit voorbeeld:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

We weten dat regel (1)O(1)tijd kost. Het is duidelijk dat we n keer rond de lus gaan, als
we kunnen bepalen door de ondergrens af te trekken van de bovengrens die online is gevonden
(1) en vervolgens 1. Omdat het lichaam, lijn (2), O(1) tijd kost, kunnen we de . verwaarlozen
tijd om j te verhogen en de tijd om j te vergelijken met n, die beide ook O(1) zijn.
De looptijd van regels (1) en (2) is dus het product van n en O(1), wat O(n)is.

Op dezelfde manier kunnen we de looptijd van de buitenste lus die uit lijnen bestaat, begrenzen
(2) tot en met (4), dat is

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

We hebben al vastgesteld dat de lus van lijnen (3) en (4) O(n) tijd kost.
We kunnen dus de O(1)-tijd verwaarlozen om i te verhogen en om te testen of i < n in
elke iteratie, met de conclusie dat elke iteratie van de buitenste lus O(n) tijd kost.

De initialisatie i = 0 van de buitenste lus en de (n + 1)ste test van de voorwaarde
ik < n neemt eveneens O(1) tijd in beslag en kan worden verwaarloosd. Ten slotte constateren we dat we gaan
n keer rond de buitenste lus, waarbij O (n) tijd wordt gebruikt voor elke iteratie, wat een totaal oplevert
O(n^2)looptijd.

---

Een meer praktisch voorbeeld.

---

Antwoord 9

Als u de volgorde van uw code empirisch wilt schatten in plaats van de code te analyseren, kunt u een reeks toenemende waarden van n invoeren en uw code timen. Zet je timings uit op een logschaal. Als de code O(x^n) is, moeten de waarden op een lijn met helling n vallen.

Dit heeft verschillende voordelen ten opzichte van het bestuderen van de code. Om te beginnen kunt u zien of u zich in het bereik bevindt waar de looptijd de asymptotische volgorde benadert. Het kan ook zijn dat een code waarvan u dacht dat het de volgorde O(x) was, in werkelijkheid de volgorde O(x^2) is, bijvoorbeeld vanwege de tijd die is besteed aan bibliotheekbezoeken.

---

Antwoord 10

In feite is het ding dat 90% van de tijd opduikt gewoon het analyseren van lussen. Heeft u enkele, dubbele, driedubbele geneste lussen? Je hebt O(n), O(n^2), O(n^3) looptijd.

Zeer zelden (tenzij je een platform schrijft met een uitgebreide basisbibliotheek (zoals bijvoorbeeld de .NET BCL of C++’s STL) zul je iets tegenkomen dat moeilijker is dan alleen maar naar je loops te kijken (voor statements, terwijl , ga naar, enz…)

---

Antwoord 11

Over het algemeen minder nuttig, denk ik, maar voor de volledigheid is er ook een Big Omega ?, dat een ondergrens definieert voor de complexiteit van een algoritme, en een Big Theta ?, die zowel een boven- als een ondergrens definieert.

---

Antwoord 12

Big O-notatie is handig omdat het gemakkelijk is om mee te werken en onnodige complicaties en details verbergt (voor een definitie van onnodig). Een mooie manier om de complexiteit van verdeel- en heersalgoritmen uit te werken is de boommethode. Stel dat u een versie van quicksort hebt met de mediaanprocedure, zodat u de array elke keer in perfect uitgebalanceerde subarrays splitst.

Bouw nu een boomstructuur die overeenkomt met alle arrays waarmee u werkt. Bij de root heb je de originele array, de root heeft twee kinderen die de subarrays zijn. Herhaal dit totdat je arrays met één element onderaan hebt.

Omdat we de mediaan in O(n)-tijd kunnen vinden en de array in O(n)-tijd in twee delen kunnen splitsen, is het werk dat op elk knooppunt wordt gedaan O(k) waarbij k de grootte van de array is. Elk niveau van de boom bevat (maximaal) de hele array, dus het werk per niveau is O(n) (de afmetingen van de subarrays tellen op tot n, en aangezien we O(k) per niveau hebben, kunnen we dit optellen) . Er zijn alleen log(n)-niveaus in de boom, aangezien we elke keer de invoer halveren.

Daarom kunnen we de hoeveelheid werk bovengrens stellen aan O(n*log(n)).

Big O verbergt echter enkele details die we soms niet kunnen negeren. Overweeg de Fibonacci-reeks te berekenen met

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

en laten we aannemen dat de a en b BigIntegers zijn in Java of iets dat willekeurig grote getallen aankan. De meeste mensen zouden zonder aarzelen zeggen dat dit een O(n)-algoritme is. De redenering is dat je n iteraties in de for-lus hebt en O(1) aan de zijkant van de lus werkt.

Maar Fibonacci-getallen zijn groot, het n-de Fibonacci-getal is exponentieel in n, dus alleen opslaan duurt in de orde van n bytes. Het optellen met grote gehele getallen kost O(n) hoeveelheid werk. Dus de totale hoeveelheid werk die in deze procedure is gedaan, is

1 + 2 + 3 + … + n = n(n-1)/2 = O(n^2)

Dus dit algoritme werkt in kwadradische tijd!

---

Antwoord 13

Breek het algoritme op in stukjes waarvan je de grote O-notatie kent, en combineer met behulp van grote O-operators. Dat is de enige manier die ik ken.

Bekijk voor meer informatie de Wikipedia-paginaover dit onderwerp.

---

Antwoord 14

Bekendheid met de algoritmen/datastructuren die ik gebruik en/of snelle blikanalyse van iteratie-nesting. De moeilijkheid is wanneer u een bibliotheekfunctie aanroept, mogelijk meerdere keren – u weet vaak niet zeker of u de functie soms onnodig aanroept of welke implementatie ze gebruiken. Misschien zouden bibliotheekfuncties een complexiteits-/efficiëntiemaatstaf moeten hebben, of dat nu Big O is of een andere metriek, die beschikbaar is in documentatie of zelfs IntelliSense.

---

Antwoord 15

Wat betreft “hoe bereken je” Big O, dit maakt deel uit van Computationele complexiteitstheorie. Voor sommige (veel) speciale gevallen kun je misschien met enkele eenvoudige heuristieken komen (zoals het vermenigvuldigen van het aantal lussen voor geneste lussen), in het bijzonder. wanneer alles wat je wilt een schatting van de bovengrens is, en je het niet erg vindt als het te pessimistisch is – wat waarschijnlijk is waar je vraag over gaat.

Als je echt je vraag voor een algoritme wilt beantwoorden, kun je het beste de theorie toepassen. Naast de simplistische “worst case” analyse vond ik Amortized analyseerg handig in de praktijk.

---

Antwoord 16

Voor het eerste geval wordt de binnenste lus n-ikeer uitgevoerd, dus het totale aantal uitvoeringen is de som voor ivanaf 0naar n-1(omdat lager dan, niet lager dan of gelijk aan) van de n-i. Je krijgt uiteindelijk n*(n + 1) / 2, dus O(n?/2) = O(n?).

Voor de 2e lus is itussen 0en ninbegrepen voor de buitenste lus; dan wordt de binnenste lus uitgevoerd wanneer jstrikt groter is dan n, wat dan onmogelijk is.

---

Antwoord 17

Naast het gebruik van de mastermethode (of een van zijn specialisaties), test ik mijn algoritmen experimenteel. Dit kan niet bewijzendat een bepaalde complexiteitsklasse wordt bereikt, maar het kan de zekerheid bieden dat de wiskundige analyse geschikt is. Om je gerust te stellen, gebruik ik codedekkingstools in combinatie met mijn experimenten, om ervoor te zorgen dat ik alle gevallen oefen.

Als een heel eenvoudig voorbeeld, zeg je dat je de snelheid van de lijstsortering van het .NET-framework wilde controleren. Je zou zoiets als het volgende kunnen schrijven en de resultaten vervolgens in Excel kunnen analyseren om er zeker van te zijn dat ze een n*log(n)-curve niet overschrijden.

In dit voorbeeld meet ik het aantal vergelijkingen, maar het is ook verstandig om de werkelijke tijd die nodig is voor elke steekproefomvang te onderzoeken. Maar dan moet je nog voorzichtiger zijn dat je alleen het algoritme meet en geen artefacten uit je testinfrastructuur meetelt.

int nCmp = 0;
System.Random rnd = new System.Random();
// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);
   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }
   System.Console.Writeline( "{0},{1}", n, nCmp );
}
// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

---

Antwoord 18

Vergeet niet om ook rekening te houden met ruimtecomplexiteit die ook een reden tot bezorgdheid kan zijn als iemand beperkte geheugenbronnen heeft. U kunt bijvoorbeeld iemand horen die een algoritme met constante ruimte wil, wat in feite een manier is om te zeggen dat de hoeveelheid ruimte die door het algoritme wordt ingenomen, niet afhangt van factoren in de code.

Soms kan de complexiteit komen van hoe vaak iets wordt aangeroepen, hoe vaak een lus wordt uitgevoerd, hoe vaak geheugen wordt toegewezen, enzovoort, is een ander onderdeel om deze vraag te beantwoorden.

Ten slotte kan grote O worden gebruikt voor worstcase-, best-case- en afschrijvingsgevallen, waarbij het over het algemeen het slechtste geval is dat wordt gebruikt om te beschrijven hoe slecht een algoritme kan zijn.

---

Antwoord 19

Wat vaak over het hoofd wordt gezien, is het verwachtegedrag van uw algoritmen. Het verandert niets aan de Big-O van uw algoritme, maar het heeft wel betrekking op de uitspraak “voortijdige optimalisatie. . ..”

Het verwachte gedrag van uw algoritme is — zeer dom — hoe snel u kunt verwachten dat uw algoritme werkt aan de gegevens die u waarschijnlijk zult zien.

Als u bijvoorbeeld naar een waarde in een lijst zoekt, is dit O(n), maar als u weet dat de meeste lijsten die u ziet uw waarde vooraf hebben, is het typische gedrag van uw algoritme sneller.

Om het echt vast te stellen, moet je de kansverdeling van je “invoerruimte” kunnen beschrijven (als je een lijst moet sorteren, hoe vaak wordt die lijst dan al gesorteerd? hoe vaak wordt het meestal gesorteerd?) Het is niet altijd haalbaar dat je dat weet, maar soms wel.

---

Antwoord 20

geweldige vraag!

Disclaimer: dit antwoord bevat valse verklaringen, zie de opmerkingen hieronder.

Als je de Big O gebruikt, heb je het over het ergste geval (later meer over wat dat betekent). Daarnaast is er hoofdletter theta voor gemiddeld geval en een grote omega voor het beste geval.

Bekijk deze site voor een mooie formele definitie van Big O: https:// xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) betekent dat er positieve constanten c en k zijn, zodat 0 ? f(n) ? cg(n) voor alle n ? k. De waarden van c en k moeten vast zijn voor de functie f en mogen niet afhankelijk zijn van n.

---

Ok, wat bedoelen we nu met “best-case” en “worst-case” complexiteiten?

Dit wordt waarschijnlijk het duidelijkst geïllustreerd aan de hand van voorbeelden. Als we bijvoorbeeld lineair zoeken gebruiken om een ​​getal in een gesorteerde array te vinden, dan is het worst casewanneer we besluiten om naar het laatste elementvan de array te zoeken, zoals dit zou neem zoveel stappen als er items in de array zijn. Het beste gevalzou zijn wanneer we zoeken naar het eerste element, aangezien we na de eerste controle klaar zouden zijn.

Het punt van al deze complexiteiten van adjectief-cases is dat we op zoek zijn naar een manier om een ​​grafiek te maken van de hoeveelheid tijd die een hypothetisch programma doorloopt tot voltooiing in termen van de grootte van bepaalde variabelen. Voor veel algoritmen kun je echter stellen dat er geen enkele tijd is voor een bepaalde invoergrootte. Merk op dat dit in tegenspraak is met de fundamentele vereiste van een functie, elke invoer mag niet meer dan één uitvoer hebben. Dus bedenken we meerderefuncties om de complexiteit van een algoritme te beschrijven. Hoewel het zoeken in een array met de grootte n soms wat tijd kost, afhankelijk van wat je zoekt in de array en in verhouding tot n, kunnen we een informatieve beschrijving van het algoritme maken met behulp van best-case, gemiddelde-case , en worstcaseklassen.

Sorry, dit is zo slecht geschreven en mist veel technische informatie. Maar hopelijk maakt het tijdcomplexiteitsklassen gemakkelijker om over na te denken. Zodra u zich hiermee op uw gemak voelt, wordt het een kwestie van uw programma doorzoeken en op zoek gaan naar dingen als for-loops die afhankelijk zijn van arraygroottes en redeneren op basis van uw gegevensstructuren, wat voor soort invoer zou resulteren in triviale gevallen en welke invoer zou resulteren in het ergste geval.

---

Antwoord 21

Ik weet niet hoe ik dit programmatisch moet oplossen, maar het eerste wat mensen doen is dat we het algoritme samplen voor bepaalde patronen in het aantal uitgevoerde bewerkingen, zeg 4n^2 + 2n + 1 we hebben 2 regels:

1. Als we een som van termen hebben, blijft de term met de grootste groeisnelheid behouden, waarbij andere termen worden weggelaten.
   
2. Als we een product van meerdere factoren hebben, worden constante factoren weggelaten.

Als we f(x) vereenvoudigen, waarbij f(x) de formule is voor het aantal uitgevoerde bewerkingen, (4n^2 + 2n + 1 hierboven uitgelegd), krijgen we de big-O-waarde [O(n^2 ) in dit geval]. Maar dit zou rekening moeten houden met Lagrange-interpolatie in het programma, wat misschien moeilijk te implementeren is. En wat als de echte big-O-waarde O(2^n) was, en we zouden zoiets als O(x^n) hebben, dan zou dit algoritme waarschijnlijk niet programmeerbaar zijn. Maar als iemand mijn ongelijk bewijst, geef me dan de code. . . .

---

Antwoord 22

Voor code A wordt de buitenste lus n+1keer uitgevoerd, de ‘1’-tijd betekent het proces dat controleert of i nog steeds aan de vereiste voldoet. En de binnenlus loopt nkeer, n-2keer…. Dus 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n?).

Voor code B, hoewel de binnenste lus niet zou ingrijpen en de foo() zou uitvoeren, zal de binnenste lus n keer worden uitgevoerd, afhankelijk van de uitvoeringstijd van de buitenste lus, namelijk O(n)

---

Antwoord 23

Ik zou de Big-O op een iets ander vlak willen uitleggen.

Big-O is alleen bedoeld om de complexiteit van de programma’s te vergelijken, wat betekent hoe snel ze groeien wanneer de input toeneemt en niet de exacte tijd die wordt besteed aan het uitvoeren van de actie.

IMHO in de big-O-formules kun je beter geen complexere vergelijkingen gebruiken (je kunt je gewoon aan die in de volgende grafiek houden.) Je kunt echter nog steeds een andere, meer nauwkeurige formule gebruiken (zoals 3^n, n^3 , …) maar meer dan dat kan soms misleidend zijn! Dus het is beter om het zo eenvoudig mogelijk te houden.

Ik wil nogmaals benadrukken dat we hier geen exacte formule voor ons algoritme willen krijgen. We willen alleen laten zien hoe het groeit als de input groeit en in die zin vergelijken met de andere algoritmen. Anders kunt u beter verschillende methoden gebruiken, zoals benchmarking.

---

Antwoord 24

Allereerst is het geaccepteerde antwoord proberen mooie, mooie dingen uit te leggen,
maar ik denk dat het opzettelijkingewikkeld maken van Big-Oh niet de oplossing is,
waarnaar programmeurs (of in ieder geval mensen zoals ik) zoeken.

Grote Oh (in het kort)

function f(text) {
  var n = text.length;
  for (var i = 0; i < n; i++) {
    f(string.slice(0, n-1))
  }
  // ... other JS logic here, which we can ignore ...
}

Grote Oh van boven is f(n) = O(n!)waarbij nstaat voor numberitems in invoerset,
en fstaat voor operationgedaan per item.

---

Big-Oh-notatie is de asymptotische bovengrens van de complexiteit van een algoritme.
Bij het programmeren: de veronderstelde tijd in het slechtste geval,
of aangenomen maximale aantal herhalingen van logica, voor de grootte van de invoer.

Berekening

Houd in gedachten (van bovenaf bedoeld) dat; We hebben alleen worst-case tijden/of maximaal aantal herhalingennodig, beïnvloed door N(grootte van invoer),
Kijk dan nog eens naar het voorbeeld van (aanvaard antwoord):

for (i = 0; i < 2*n; i += 2) {  // line 123
    for (j=n; j > i; j--) {     // line 124
        foo();                  // line 125
    }
}

1. Begin met dit zoekpatroon:

   • Vind de eerste regel dat Nherhaalgedrag veroorzaakte,
   • Of veroorzaakte toename van uitgevoerde logica,
   • Maar constant of niet, negeer alles voor die regel.

2. Het lijkt erop dat regel honderddrieëntwintig is wat we zoeken 😉

   • Op het eerste gezicht lijkt de lijn 2*nmax-looping te hebben.
   • Maar als we nog een keer kijken, zien we i += 2(en die helft wordt overgeslagen).
   • Dus max. herhaling is gewoon n, schrijf het op, zoals f(n) = O( n maar sluit haakjes nog niet.

3. Herhaal de zoekopdracht tot het einde van de methode en vind de volgende regel die overeenkomt met ons zoekpatroon, hier is dat regel 124

   • Wat lastig is, vanwege de vreemde toestand en omgekeerde looping.
   • Maar nadat we eraan hebben herinnerd dat we alleen het maximale aantal herhalingen moeten overwegen (of in het slechtste geval).
   • Het is net zo eenvoudig als zeggen: “Reverse-Loop jbegint met j=n, heb ik gelijk? ja, nlijkt te zijn maximaal aantal herhalingen”, dus voeg ntoe aan het einde van de vorige opschrijving, maar zoals “( n ” (in plaats van + n, zoals dit is binnen de vorige lus) en sluit alleen haakjes als we iets buiten de vorige lus vinden.

Zoeken voltooid! waarom? omdat regel 125 (of iets later) niet overeenkomt met ons zoekpatroon.
We kunnen nu elk haakje sluiten (opengelaten in ons opschrijven), wat resulteert in het onderstaande:

f(n) = O( n( n ) )

Probeer het gedeelte “n( n )” verder in te korten, zoals:

• n( n) = n * n
• = n²
• Sluit het ten slotte af met de Big Oh-notatie, zoals O(n²)of O(n^2) zonder opmaak.