Groot O, hoe bereken/benader jy dit?

StackOverflow https://stackoverflow.com/questions/3255

Vra

Die meeste mense met 'n graad in CS sal beslis weet wat Groot O staan ​​vir.Dit help ons om te meet hoe (on)doeltreffend 'n algoritme werklik is en of jy weet in in watter kategorie lê die probleem wat jy probeer oplos jy kan uitvind of dit nog moontlik is om daardie bietjie ekstra prestasie uit te druk.1

Maar ek is nuuskierig, hoe doen jy die kompleksiteit van jou algoritmes te bereken of te benader?

1 maar soos hulle sê, moenie dit oordoen nie, voortydige optimalisering is die wortel van alle kwaad, en optimalisering sonder 'n geregverdigde oorsaak behoort daardie naam ook te verdien.

Was dit nuttig?

Oplossing

Ek sal my bes doen om dit hier op eenvoudige terme te verduidelik, maar wees gewaarsku dat hierdie onderwerp my studente 'n paar maande neem om uiteindelik te begryp.Jy kan meer inligting oor die Hoofstuk 2 van die Datastrukture en algoritmes in Java boek.

Daar is geen meganiese prosedure wat gebruik kan word om die BigOh te kry.

As 'n "kookboek", om die BigOh uit 'n stukkie kode moet jy eers besef dat jy 'n wiskundige formule skep om te tel hoeveel stappe van berekeninge uitgevoer word, gegewe 'n inset van een of ander grootte.

Die doel is eenvoudig:om algoritmes vanuit 'n teoretiese oogpunt te vergelyk, sonder dat dit nodig is om die kode uit te voer.Hoe minder die aantal stappe, hoe vinniger is die algoritme.

Byvoorbeeld, kom ons sê jy het hierdie stukkie kode:

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
}

Hierdie funksie gee die som van al die elemente van die skikking terug, en ons wil 'n formule skep om die berekeningskompleksiteit van daardie funksie:

Number_Of_Steps = f(N)

So ons het f(N), 'n funksie om die aantal berekeningstappe te tel.Die inset van die funksie is die grootte van die struktuur om te verwerk.Dit beteken dat hierdie funksie soos genoem word:

Number_Of_Steps = f(data.length)

Die parameter N neem die data.length waarde.Nou het ons die werklike definisie van die funksie nodig f().Dit word gedoen vanaf die bronkode, waarin elke interessante reël van 1 tot 4 genommer is.

Daar is baie maniere om die BigOh te bereken.Van hierdie punt af gaan ons aanneem dat elke sin wat nie afhang van die grootte van die invoerdata 'n konstante neem C getalberekeningstappe.

Ons gaan die individuele aantal stappe van die funksie byvoeg, en nie die plaaslike veranderlike verklaring of die terugkeerstelling hang af van die grootte van die data skikking.

Dit beteken dat reëls 1 en 4 elk C aantal stappe neem, en die funksie is ietwat soos volg:

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

Die volgende deel is om die waarde van die te definieer for verklaring.Onthou dat ons die aantal berekeningstappe tel, wat beteken dat die liggaam van die for verklaring uitgevoer word N tye.Dit is dieselfde as om by te voeg C, N tye:

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

Daar is geen meganiese reël om te tel hoeveel keer die liggaam van die for uitgevoer word, moet jy dit tel deur te kyk wat die kode doen.Om die berekeninge te vereenvoudig, ignoreer ons die veranderlike inisialisering, toestand en inkrement dele van die for verklaring.

Om die werklike BigOh te kry, benodig ons die Asimptotiese analise van die funksie.Dit word ongeveer so gedoen:

  1. Neem al die konstantes weg C.
  2. Van f() kry die polinoom in sy standard form.
  3. Verdeel die terme van die polinoom en sorteer hulle volgens die groeitempo.
  4. Hou die een wat groter word wanneer N benaderings infinity.

Ons f() het twee terme:

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

Die wegneem van al die C konstantes en oortollige dele:

f(N) = 1 + N ^ 1

Sedert die laaste kwartaal is die een wat groter word wanneer f() nader oneindigheid (dink aan perke) dit is die BigOh-argument, en die sum() funksie het 'n BigOh van:

O(N)

Daar is 'n paar truuks om 'n paar moeilike op te los:gebruik opsommings wanneer jy kan.

As 'n voorbeeld kan hierdie kode maklik opgelos word deur opsommings te gebruik:

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

Die eerste ding wat jy gevra moes word, is die volgorde van uitvoering van foo().Terwyl die gewone is om te wees O(1), moet jy jou professore daaroor vra. O(1) beteken (byna, meestal) konstant C, onafhanklik van die grootte N.

Die for stelling oor die sin nommer een is lastig.Terwyl die indeks eindig by 2 * N, word die verhoging met twee gedoen.Dit beteken dat die eerste for word slegs uitgevoer N stappe, en ons moet die telling deur twee deel.

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

Die sinnommer twee is selfs moeiliker aangesien dit afhang van die waarde van i.Kyk:die indeks i neem die waardes:0, 2, 4, 6, 8, ..., 2 * N, en die tweede for tereggestel word:N keer die eerste een, N - 2 die tweede, N - 4 die derde...tot by die N / 2 stadium, waarop die tweede for word nooit tereggestel nie.

Op formule beteken dit:

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

Weereens, ons tel die aantal stappe.En per definisie moet elke opsomming altyd by een begin, en eindig by 'n getal groter-of-gelyk as een.

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

(Ons neem aan dat foo() is O(1) en neem C stappe.)

Ons het 'n probleem hier:wanneer i neem die waarde N / 2 + 1 opwaarts, eindig die innerlike Opsomming op 'n negatiewe getal!Dis onmoontlik en verkeerd.Ons moet die opsomming in twee verdeel, aangesien dit die spilpunt is op die oomblik i neem N / 2 + 1.

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 )

Sedert die deurslaggewende oomblik i > N / 2, die innerlike for sal nie uitgevoer word nie, en ons aanvaar 'n konstante C-uitvoeringskompleksiteit op sy liggaam.

Nou kan die opsommings vereenvoudig word deur 'n paar identiteitsreëls te gebruik:

  1. Opsomming(w van 1 tot N)( C ) = N * C
  2. Summation(w from 1 to N)( A (+/-) B ) = Summation(w from 1 to N)( A ) (+/-) Summation(w from 1 to N)( B )
  3. Sommasie(w van 1 tot N)( w * C ) = C * Sommasie(w van 1 tot N)( w ) (C is 'n konstante, onafhanklik van w)
  4. Opsomming(w van 1 tot N)( w ) = (N * (N + 1)) / 2

Die toepassing van algebra:

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 die BigOh is:

O(N²)

Ander wenke

Groot O gee die boonste grens vir tydkompleksiteit van 'n algoritme.Dit word gewoonlik saam met die verwerking van datastelle (lyste) gebruik, maar kan elders gebruik word.

'n Paar voorbeelde van hoe dit in C-kode gebruik word.

Gestel ons het 'n skikking van n elemente

int array[n];

As ons toegang tot die eerste element van die skikking wou verkry, sou dit O(1) wees, aangesien dit nie saak maak hoe groot die skikking is nie, dit neem altyd dieselfde konstante tyd om die eerste item te kry.

x = array[0];

As ons 'n nommer in die lys wil vind:

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

Dit sal O(n) wees aangesien ons hoogstens deur die hele lys sal moet kyk om ons nommer te vind.Die Big-O is steeds O(n) alhoewel ons dalk ons ​​nommer met die eerste probeerslag vind en een keer deur die lus hardloop omdat Big-O die boonste grens vir 'n algoritme beskryf (omega is vir ondergrens en theta is vir stywe grens) .

Wanneer ons by geneste lusse kom:

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

Dit is O(n^2) aangesien ons vir elke deurgang van die buitenste lus ( O(n) ) weer deur die hele lys moet gaan sodat die n's vermenigvuldig wat ons met n kwadraat laat.

Dit krap skaars die oppervlak, maar wanneer jy by die ontleding van meer komplekse algoritmes kom, kom komplekse wiskunde met bewyse ter sprake.Hoop dit maak jou ten minste vertroud met die basiese beginsels.

Alhoewel dit nuttig is om te weet hoe om die Big O-tyd vir jou spesifieke probleem uit te vind, kan die wete van sommige algemene gevalle jou help om besluite in jou algoritme te neem.

Hier is 'n paar van die mees algemene gevalle, opgehef uit http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O(1) - Bepaal of 'n getal ewe of onewe is;met behulp van 'n konstante-grootte opsoektabel of hash-tabel

O(logn) - Vind 'n item in 'n gesorteerde skikking met 'n binêre soektog

O(n) - Vind 'n item in 'n ongesorteerde lys;byvoeging van twee n-syfergetalle

O(n2) - Vermenigvuldiging van twee n-syfergetalle met 'n eenvoudige algoritme;byvoeging van twee n×n matrikse;borrel sorteer of invoeg sorteer

O(n3) - Vermenigvuldiging van twee n×n matrikse deur eenvoudige algoritme

O(cn) - Vind die (presiese) oplossing vir die reisende verkoopsman probleem deur gebruik te maak van dinamiese programmering;bepaal of twee logiese stellings ekwivalent is deur brute krag te gebruik

O(n!) - Los die reisende verkoopsman-probleem op via brute-force-soektog

O(nn) - Word dikwels in plaas van O(n!) gebruik om eenvoudiger formules vir asimptotiese kompleksiteit af te lei

Klein herinnering:die big O notasie word gebruik om aan te dui asimptoties kompleksiteit (dit wil sê wanneer die grootte van die probleem tot oneindig toeneem), en dit verberg 'n konstante.

Dit beteken dat tussen 'n algoritme in O(n) en een in O(n2), is die vinnigste nie altyd die eerste een nie (alhoewel daar altyd 'n waarde van n bestaan ​​sodat vir probleme van grootte >n, die eerste algoritme die vinnigste is).

Let daarop dat die verborge konstante baie afhang van die implementering!

Ook, in sommige gevalle is die looptyd nie 'n deterministiese funksie van die grootte n van die invoer.Neem byvoorbeeld sortering deur gebruik te maak van vinnige sortering:die tyd wat nodig is om 'n skikking van n elemente te sorteer, is nie 'n konstante nie, maar hang af van die beginkonfigurasie van die skikking.

Daar is verskillende tydskompleksiteite:

  • Ergste geval (gewoonlik die eenvoudigste om uit te vind, hoewel nie altyd baie betekenisvol nie)

  • Gemiddelde geval (gewoonlik baie moeiliker om uit te vind ...)

  • ...

'n Goeie inleiding is 'n Inleiding tot die analise van algoritmes deur R.Sedgewick en P.Flajolet.

Soos jy se, premature optimisation is the root of all evil, en (indien moontlik) profilering moet regtig altyd gebruik word wanneer kode geoptimaliseer word.Dit kan jou selfs help om die kompleksiteit van jou algoritmes te bepaal.

As ek die antwoorde hier sien, dink ek ons ​​kan tot die gevolgtrekking kom dat die meeste van ons wel die volgorde van die algoritme benader deur kyk daaraan en gebruik gesonde verstand in plaas daarvan om dit te bereken met byvoorbeeld die meester metode soos ons op universiteit gedink is.Met dit gesê, moet ek byvoeg dat selfs die professor ons (later) aangemoedig het om eintlik dink daaroor in plaas daarvan om dit net te bereken.

Ek wil ook byvoeg hoe dit gedoen word rekursiewe funksies:

veronderstel ons het 'n funksie soos (skema kode):

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

wat rekursief die faktoriaal van die gegewe getal bereken.

Die eerste stap is om die prestasie-eienskap vir te probeer bepaal slegs die liggaam van die funksie in hierdie geval word niks besonders in die liggaam gedoen nie, net 'n vermenigvuldiging (of die terugkeer van die waarde 1).

Sodat die prestasie vir die liggaam is:O(1) (konstant).

Volgende probeer en bepaal dit vir die aantal rekursiewe oproepe.In hierdie geval het ons n-1 rekursiewe oproepe.

Sodat die prestasie vir die rekursiewe oproepe is:O(n-1) (volgorde is n, aangesien ons die onbeduidende dele weggooi).

Sit dan daardie twee saam en jy het dan die prestasie vir die hele rekursiewe funksie:

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

Petrus, om te antwoord jou geopperde kwessies; die metode wat ek hier beskryf, hanteer dit eintlik redelik goed.Maar hou in gedagte dat dit steeds 'n benadering en nie 'n volledige wiskundig korrekte antwoord nie.Die metode wat hier beskryf word, is ook een van die metodes wat ons op universiteit geleer is, en as ek reg onthou is dit vir baie meer gevorderde algoritmes gebruik as die faktoriaal wat ek in hierdie voorbeeld gebruik het.
Dit hang natuurlik alles af van hoe goed jy die looptyd van die liggaam van die funksie en die aantal rekursiewe oproepe kan skat, maar dit is net so waar vir die ander metodes.

As jou koste 'n polinoom is, hou net die hoogste-orde term, sonder sy vermenigvuldiger.Bv.:

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

Dit werk nie vir oneindige reekse nie, let wel.Daar is geen enkele resep vir die algemene geval nie, maar vir sommige algemene gevalle geld die volgende ongelykhede:

O(log N) < O(N) < O(N Meld N) < O(N2) < O(Nk) < O(en) < O(n!)

Ek dink daaroor in terme van inligting.Enige probleem bestaan ​​uit die aanleer van 'n sekere aantal bisse.

Jou basiese hulpmiddel is die konsep van besluitnemingspunte en hul entropie.Die entropie van 'n besluitpunt is die gemiddelde inligting wat dit vir jou sal gee.Byvoorbeeld, as 'n program 'n besluitpunt met twee takke bevat, is sy entropie die som van die waarskynlikheid van elke tak maal die log2 van die omgekeerde waarskynlikheid van daardie tak.Dit is hoeveel jy leer deur daardie besluit uit te voer.

Byvoorbeeld, 'n if stelling met twee takke, albei ewe waarskynlik, het 'n entropie van 1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1.So sy entropie is 1 bietjie.

Gestel jy soek 'n tabel van N items, soos N=1024.Dit is 'n 10-bis probleem omdat log(1024) = 10 bisse.So as jy dit kan deursoek met IF-stellings wat ewe waarskynlike uitkomste het, moet dit 10 besluite neem.

Dit is wat jy kry met binêre soektog.

Gestel jy doen lineêre soektog.Jy kyk na die eerste element en vra of dit die een is wat jy wil hê.Die waarskynlikhede is 1/1024 wat dit is, en 1023/1024 dat dit nie is nie.Die entropie van daardie besluit is 1/1024*log(1024/1) + 1023/1024 * log(1024/1023) = 1/1024 * 10 + 1023/1024 * ongeveer 0 = ongeveer .01 bis.Jy het baie min geleer!Die tweede besluit is nie veel beter nie.Dit is hoekom lineêre soektog so stadig is.In werklikheid is dit eksponensieel in die aantal stukkies wat jy moet leer.

Gestel jy doen indeksering.Gestel die tabel is vooraf in baie bakke gesorteer, en jy gebruik sommige van al die stukkies in die sleutel om direk na die tabelinskrywing te indekseer.As daar 1024 bakkies is, is die entropie 1/1024 * log(1024) + 1/1024 * log(1024) + ...vir al 1024 moontlike uitkomste.Dit is 1/1024 * 10 keer 1024 uitkomste, of 10 stukkies entropie vir daardie een indekseringsbewerking.Dit is hoekom indeksering soek vinnig is.

Dink nou aan sortering.Jy het N items, en jy het 'n lys.Vir elke item moet jy soek na waar die item in die lys gaan, en dit dan by die lys voeg.So sorteer neem ongeveer N keer die aantal stappe van die onderliggende soektog.

So sorteer gebaseer op binêre besluite met ongeveer ewe waarskynlike uitkomste, neem almal ongeveer O(N log N) stappe.'n O(N)-sorteeralgoritme is moontlik as dit gebaseer is op indekseringsoektog.

Ek het gevind dat byna alle algoritmiese prestasiekwessies op hierdie manier gekyk kan word.

Kom ons begin van die begin af.

Aanvaar eerstens die beginsel dat sekere eenvoudige bewerkings op data in gedoen kan word O(1) tyd, dit wil sê in tyd wat onafhanklik is van die grootte van die inset.Hierdie primitiewe bewerkings in C bestaan ​​uit

  1. Rekenkundige bewerkings (bv.+ of %).
  2. Logiese bewerkings (bv. &&).
  3. Vergelykingsbewerkings (bv. <=).
  4. Struktuurtoegangsbedrywighede (bv.Array-indeksering soos 'n [i], of wyser volg met die-> operateur).
  5. Eenvoudige opdrag soos die kopiëring van 'n waarde in 'n veranderlike.
  6. Oproepe na biblioteekfunksies (bv. scanf, printf).

Die regverdiging vir hierdie beginsel vereis 'n gedetailleerde studie van die masjieninstruksies (primitiewe stappe) van 'n tipiese rekenaar.Elkeen van die beskryfde bewerkings kan met 'n klein aantal masjieninstruksies gedoen word;dikwels is net een of twee instruksies nodig.As gevolg hiervan kan verskeie soorte stellings in C uitgevoer word O(1) tyd, dit wil sê in 'n konstante hoeveelheid tyd onafhanklik van insette.Hierdie eenvoudige sluit in

  1. Opdragstellings wat nie funksie-oproepe in hul uitdrukkings behels nie.
  2. Lees stellings.
  3. Skryf stellings wat nie funksie-oproepe vereis om argumente te evalueer nie.
  4. Die springverklarings breek, gaan voort, gaan, en gee uitdrukking, waar uitdrukking nie 'n funksieoproep bevat nie.

In C word baie vir-lusse gevorm deur 'n indeksveranderlike tot 'n mate van waarde te initialiseer en daardie veranderlike elke keer om die lus te verhoog.Die voor-lus eindig wanneer die indeks 'n limiet bereik.Byvoorbeeld, die for-lus 

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;
}

gebruik indeksveranderlike i.Dit kom elke keer by 1 in om die lus, en die iterasies stop as ek n - 1 bereik.

Fokus egter vir die oomblik op die eenvoudige vorm van for-lus, waar die verskil tussen die finale en aanvanklike waardes, gedeel deur die hoeveelheid waarmee die indeksveranderlike verhoog word, vertel ons hoeveel keer ons om die lus gaan.Daardie telling is presies, tensy daar maniere is om die lus te verlaat via 'n sprongstelling;dit is in elk geval 'n boonste grens van die aantal iterasies.

Byvoorbeeld, die for-lus herhaal ((n − 1) − 0)/1 = n − 1 times, Aangesien 0 die aanvanklike waarde van i, n - 1 is die hoogste waarde wat I bereik het (dit wil sê as ek n - 1 bereik, stop die lus en geen iterasie kom voor met i = n - 1), en 1 word bygevoeg by Ek by elke iterasie van die lus.

In die eenvoudigste geval, waar die tyd wat in die lusliggaam spandeer word, dieselfde is vir elke iterasie, Ons kan die groot-Oh-boonste boonste na die liggaam vermenigvuldig met die aantal kere rondom die lus.Streng gesproke moet ons dan Voeg O (1) tyd by om die lusindeks te initialiseer en O (1) tyd vir die eerste vergelyking van die lusindeks met die limiet, want ons toets nog een keer as wat ons om die lus gaan.Tensy dit moontlik is om die lus nul keer uit te voer, is die tyd om die lus te initialiseer en die limiet een keer te toets, 'n lae-orde-term wat volgens die opsommingsreël laat val kan word.

Kyk nou na hierdie voorbeeld:

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

Ons weet dit reël (1) neem O(1) tyd.Dit is duidelik dat ons om die lus n tye gaan, soos ons kan bepaal deur die onderste limiet van die boonste limiet op lyn (1) af te trek en dan 1 by te voeg.Aangesien die liggaam, lyn (2), o (1) tyd neem, kan ons die tyd verwaarloos om J en die tyd om j met N te vergelyk, te vergelyk, wat ook O (1) is.Dus, die looptyd van lyne (1) en (2) is die produk van n en O(1), wat is O(n).

Net so kan ons die looptyd van die buitenste lus wat bestaan ​​uit lyne (2) tot (4), wat is

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

Ons het reeds vasgestel dat die lus van lyne (3) en (4) O(n) tyd neem.Dus kan ons die o (1) tyd om I in te verhoog en om te toets of ek in elke iterasie te toets, tot die gevolgtrekking dat elke iterasie van die buitenste lus o (n) tyd neem.

Die initialisering i = 0 van die buitenste lus en die (n + 1) ST -toets van die toestand i <n neem ook o (1) tyd en kan verwaarloos word.Laastens neem ons kennis dat ons in die buitenste lus rondloop, en dit neem O (n) tyd vir elke iterasie, en gee 'n totaalO(n^2) looptyd.

'n Meer praktiese voorbeeld.

enter image description here

As jy die volgorde van jou kode empiries wil skat eerder as deur die kode te analiseer, kan jy 'n reeks toenemende waardes van n inhou en jou kode tyd.Teken jou tydsberekeninge op 'n log skaal.As die kode O(x^n is), moet die waardes op 'n lyn van helling n val.

Dit het verskeie voordele bo net om die kode te bestudeer.Vir een ding kan jy sien of jy in die reeks is waar die looptyd sy asimptotiese volgorde nader.Jy kan ook vind dat een of ander kode wat jy gedink het orde O(x) is, werklik orde O(x^2 is), byvoorbeeld, as gevolg van tyd wat in biblioteekoproepe spandeer word.

Basies is die ding wat 90% van die tyd opduik net om lusse te ontleed.Het jy enkel-, dubbel-, drievoudig geneste lusse?Die jy het O(n), O(n^2), O(n^3) looptyd.

Baie selde (tensy jy 'n platform skryf met 'n uitgebreide basisbiblioteek (soos byvoorbeeld die .NET BCL, of C++ se STL) sal jy enigiets teëkom wat moeiliker is as om net na jou lusse te kyk (vir stellings, terwyl, goto, ens...)

Breek die algoritme af in stukke waarvoor jy die groot O-notasie ken, en kombineer deur groot O-operateurs.Dit is die enigste manier waarvan ek weet.

Vir meer inligting, kyk na die Wikipedia-bladsy op die onderwerp.

Groot O-notasie is nuttig omdat dit maklik is om mee te werk en onnodige komplikasies en besonderhede verberg (vir een of ander definisie van onnodig).Een goeie manier om die kompleksiteit van verdeel-en-oorwin-algoritmes uit te werk, is die boommetode.Kom ons sê jy het 'n weergawe van quicksort met die mediaan prosedure, sodat jy elke keer die skikking in perfek gebalanseerde subskikkings verdeel.

Bou nou 'n boom wat ooreenstem met al die skikkings waarmee jy werk.By die wortel het jy die oorspronklike skikking, die wortel het twee kinders wat die subskikkings is.Herhaal dit totdat jy enkele element skikkings aan die onderkant het.

Aangesien ons die mediaan in O(n) tyd kan vind en die skikking in twee dele in O(n) tyd kan verdeel, is die werk wat by elke nodus gedoen word O(k) waar k die grootte van die skikking is.Elke vlak van die boom bevat (hoogstens) die hele skikking, so die werk per vlak is O(n) (die groottes van die subskikkings tel n op, en aangesien ons O(k) per vlak het, kan ons dit optel) .Daar is slegs log(n) vlakke in die boom, aangesien ons elke keer die invoer halveer.

Daarom kan ons die hoeveelheid werk bogrens met O(n*log(n)).

Big O versteek egter 'n paar besonderhede wat ons soms nie kan ignoreer nie.Oorweeg om die Fibonacci-ry te bereken met

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

en laat ons net aanvaar die a en b is GrootGeheelgetalle in Java of iets wat arbitrêr groot getalle kan hanteer.Die meeste mense sal sê dit is 'n O(n)-algoritme sonder om te deins.Die redenasie is dat jy n iterasies in die for-lus het en O(1) werk in die kant van die lus.

Maar Fibonacci-getalle is groot, die n-de Fibonacci-getal is eksponensieel in n so net om dit te stoor sal die orde van n grepe aanneem.Om optelling met groot heelgetalle uit te voer sal O(n) hoeveelheid werk verg.Dus is die totale hoeveelheid werk wat in hierdie prosedure gedoen is

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

So hierdie algoritme loop in kwadradiese tyd!

Bekendheid met die algoritmes/datastrukture wat ek gebruik en/of vinnige blikanalise van iterasie nesting.Die moeilikheid is wanneer jy 'n biblioteekfunksie oproep, moontlik verskeie kere - jy kan dikwels onseker wees of jy die funksie soms onnodig oproep of watter implementering hulle gebruik.Miskien moet biblioteekfunksies 'n kompleksiteit/doeltreffendheidsmaatstaf hê, hetsy dit Big O of 'n ander maatstaf is, wat beskikbaar is in dokumentasie of selfs IntelliSense.

Minder bruikbaar oor die algemeen, dink ek, maar volledigheidshalwe is daar ook 'n Groot Omega Ω, wat 'n ondergrens op 'n algoritme se kompleksiteit definieer, en a Groot Theta Θ, wat beide 'n boonste en onderste grens definieer.

Wat betref "hoe bereken jy" Big O, dit is deel van Rekenkundige kompleksiteitsteorie.Vir sommige (baie) spesiale gevalle kan jy dalk met 'n paar eenvoudige heuristieke kom (soos die vermenigvuldiging van lustellings vir geneste lusse), esp.wanneer al wat jy wil hê enige bogrens skatting is, en jy nie omgee as dit te pessimisties is nie - wat ek dink waarskynlik is waaroor jou vraag gaan.

As jy regtig jou vraag vir enige algoritme wil beantwoord, is die beste wat jy kan doen om die teorie toe te pas.Behalwe van simplistiese "ergste geval" analise wat ek gevind het Geamortiseerde analise baie nuttig in die praktyk.

Vir die 1ste geval word die binnelus uitgevoer n-i keer, dus is die totale aantal teregstellings die som vir i gaan van 0 aan n-1 (omdat laer as, nie laer as of gelyk is nie) van die n-i.Jy kry uiteindelik n*(n + 1) / 2, so O(n²/2) = O(n²).

Vir die 2de lus, i is tussen 0 en n ingesluit vir die buitenste lus;dan word die binnelus uitgevoer wanneer j is streng groter as n, wat dan onmoontlik is.

Benewens die gebruik van die meestermetode (of een van sy spesialisasies), toets ek my algoritmes eksperimenteel.Dit kan nie bewys dat enige spesifieke kompleksiteitsklas bereik word, maar dit kan gerusstelling verskaf dat die wiskundige analise toepaslik is.Om te help met hierdie gerusstelling, gebruik ek kodedekkingnutsmiddels in samewerking met my eksperimente, om te verseker dat ek al die gevalle oefen.

As 'n baie eenvoudige voorbeeld sê jy wou 'n gesonde verstandkontrole doen oor die spoed van die .NET-raamwerk se lyssoort.Jy kan iets soos die volgende skryf en dan die resultate in Excel ontleed om seker te maak dat hulle nie 'n n*log(n)-kromme oorskry nie.

In hierdie voorbeeld meet ek die aantal vergelykings, maar dit is ook verstandig om die werklike tyd wat benodig word vir elke steekproefgrootte te ondersoek.Maar dan moet jy selfs meer versigtig wees dat jy net die algoritme meet en nie artefakte van jou toetsinfrastruktuur insluit nie.

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);

Moenie vergeet om ook voorsiening te maak vir ruimtekompleksiteite wat ook 'n rede tot kommer kan wees as 'n mens beperkte geheuebronne het nie.So byvoorbeeld hoor jy iemand wat 'n konstante spasie-algoritme wil hê, wat basies 'n manier is om te sê dat die hoeveelheid spasie wat deur die algoritme geneem word nie afhang van enige faktore binne die kode nie.

Soms kan die kompleksiteit kom van hoeveel keer iets genoem word, hoe gereeld 'n lus uitgevoer word, hoe gereeld geheue toegeken word, ensovoorts is 'n ander deel om hierdie vraag te beantwoord.

Laastens kan groot O gebruik word vir slegste geval, beste geval en amortisasie gevalle waar dit oor die algemeen die ergste geval is wat gebruik word om te beskryf hoe sleg 'n algoritme kan wees.

Wat dikwels oor die hoof gesien word, is die verwag gedrag van jou algoritmes. Dit verander nie die Big-O van jou algoritme nie, maar dit hou verband met die stelling "voortydige optimalisering...."

Verwagte gedrag van jou algoritme is - baie stomgeslaan - hoe vinnig jy kan verwag dat jou algoritme sal werk op data wat jy heel waarskynlik sal sien.

As jy byvoorbeeld na 'n waarde in 'n lys soek, is dit O(n), maar as jy weet dat die meeste lyste wat jy sien jou waarde voorop het, is tipiese gedrag van jou algoritme vinniger.

Om dit regtig vas te stel, moet jy die waarskynlikheidsverdeling van jou "invoerspasie" kan beskryf (as jy 'n lys moet sorteer, hoe gereeld gaan daardie lys reeds gesorteer word?hoe gereeld word dit heeltemal omgekeer?hoe gereeld word dit meestal gesorteer?) Dis nie altyd haalbaar dat jy dit weet nie, maar soms wel.

goeie vraag!

Vrywaring:hierdie antwoord bevat vals stellings sien die kommentaar hieronder.

As jy die Big O gebruik, praat jy van die ergste geval (meer oor wat dit later beteken).Daarbenewens is daar hoofletter theta vir gemiddelde kassie en 'n groot omega vir die beste geval.

Kyk na hierdie webwerf vir 'n pragtige formele definisie van Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) beteken daar is positiewe konstantes c en k, sodanig dat 0 ≤ f(n) ≤ cg(n) vir alle n ≥ k.Die waardes van c en k moet vasgestel word vir die funksie f en moet nie van n afhang nie.

Ok, so nou, wat bedoel ons met "beste-geval" en "ergste-geval" kompleksiteite?

Dit word waarskynlik die duidelikste geïllustreer deur voorbeelde.As ons byvoorbeeld lineêre soektog gebruik om 'n getal in 'n gesorteerde skikking te vind, dan is die ergste geval is wanneer ons besluit om soek na die laaste element van die skikking aangesien dit soveel stappe sal neem as wat daar items in die skikking is.Die beste geval sou wees wanneer ons soek na die eerste element aangesien ons na die eerste kontrole klaar sou wees.

Die punt van al hierdie byvoeglike naamwoord-geval kompleksiteit is dat ons op soek is na 'n manier om die hoeveelheid tyd wat 'n hipotetiese program loop tot voltooiing te grafiek in terme van die grootte van spesifieke veranderlikes.Vir baie algoritmes kan jy egter argumenteer dat daar nie 'n enkele tyd is vir 'n bepaalde grootte van insette nie.Let daarop dat dit in stryd is met die fundamentele vereiste van 'n funksie, enige inset moet nie meer as een uitset hê nie.So kom ons met veelvuldig funksies om 'n algoritme se kompleksiteit te beskryf.Nou, al kan die soektog na 'n skikking van grootte n wisselende hoeveelhede tyd neem, afhangende van waarna jy in die skikking soek en proporsioneel tot n afhang, kan ons 'n insiggewende beskrywing van die algoritme skep deur die beste-geval, gemiddelde-geval te gebruik. , en slegste-geval klasse.

Jammer dit is so swak geskryf en kort baie tegniese inligting.Maar hopelik sal dit makliker wees om oor tydkompleksiteitsklasse na te dink.Sodra jy gemaklik daarmee raak, word dit 'n eenvoudige saak om deur jou program te ontleed en te soek na dinge soos vir-lusse wat afhang van skikkingsgroottes en redenasie gebaseer op jou datastrukture watter soort insette sal lei tot onbenullige gevalle en watter insette sal lei in die ergste gevalle.

Ek weet nie hoe om dit programmaties op te los nie, maar die eerste ding wat mense doen, is dat ons die algoritme monster vir sekere patrone in die aantal bewerkings wat gedoen is, sê 4n^2 + 2n + 1 ons het 2 reëls:

  1. As ons 'n som van terme het, word die term met die grootste groeikoers behou, met ander terme weggelaat.
  2. As ons 'n produk van verskeie faktore het, word konstante faktore weggelaat.

As ons f(x) vereenvoudig, waar f(x) die formule is vir die aantal bewerkings wat gedoen is, (4n^2 + 2n + 1 hierbo verduidelik), kry ons die groot-O-waarde [O(n^2) in hierdie geval].Maar dit sal rekening moet hou met Lagrange-interpolasie in die program, wat moeilik kan wees om te implementeer.En wat as die werklike groot-O-waarde O(2^n) was, en ons het dalk iets soos O(x^n), so hierdie algoritme sou waarskynlik nie programmeerbaar wees nie.Maar as iemand my verkeerd bewys, gee my die kode....

Vir kode A sal die buitenste lus vir n+1 keer beteken die '1'-tyd die proses wat kontroleer of i steeds aan die vereiste voldoen.En binnelus loop n tye, n-2 tye....Dus,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

Vir kode B, alhoewel binnelus nie sou intree en die foo( uitvoer nie), sal die binnelus vir n keer uitgevoer word, hang af van die buitelusuitvoeringstyd, wat O(n) is.

Ek wil graag die Big-O in 'n bietjie ander aspek verduidelik.

Big-O is net om die kompleksiteit van die programme te vergelyk, wat beteken hoe vinnig hulle groei wanneer die insette toeneem en nie die presiese tyd wat spandeer word om die aksie uit te voer nie.

IMHO in die groot-O-formules moet jy beter nie meer komplekse vergelykings gebruik nie (jy kan net by dié in die volgende grafiek bly.) Maar jy kan steeds ander meer presiese formules gebruik (soos 3^n, n^3, .. .) maar meer as dit kan soms misleidend wees!Dit is dus beter om dit so eenvoudig as moontlik te hou.

enter image description here

Ek wil weereens beklemtoon dat ons hier nie 'n presiese formule vir ons algoritme wil kry nie.Ons wil net wys hoe dit groei wanneer die insette groei en vergelyk met die ander algoritmes in daardie sin.Andersins sal jy beter verskillende metodes soos bench-marking gebruik.

Gelisensieer onder: CC-BY-SA met toeskrywing
Nie verbonde aan StackOverflow
scroll top