[Powered by Google Translate] Du har sikkert hørt folk snakke om en rask og effektiv algoritme for utføring av din bestemt oppgave, men hva betyr det for en algoritme for å være rask eller effektiv? Vel, det er ikke snakk om en måling i sanntid, som sekunder eller minutter. Dette er fordi maskinvare og programvare varierer drastisk. Mitt program kan kjøre saktere enn din, fordi jeg kjører den på en eldre datamaskin, eller fordi jeg tilfeldigvis skal spille et online dataspill på samme tid, som den samler min hukommelse, eller jeg kan kjøre mitt program gjennom forskjellig programvare som kommuniserer med maskinen annerledes på et lavt nivå. Det er som å sammenligne epler og appelsiner. Bare fordi min tregere datamaskin tar lengre tid enn din for å gi tilbake et svar betyr ikke at du har den mer effektiv algoritme. 

Så, siden vi ikke kan sammenlikne kjøretidsfiler av programmer i løpet av sekunder eller minutter, hvordan sammenligne vi to forskjellige algoritmer uavhengig av deres maskinvare eller programvare-miljøet? Å skape en mer enhetlig måte å måle algoritmisk effektivitet, dataforskere og matematikere har utviklet konsepter for måling den asymptotiske kompleksiteten av et program og en notasjon som kalles "Big Ohnotation ' for å beskrive dette. Den formelle definisjon er at en funksjon f (x) kjører på i størrelsesorden g (x) hvis det eksisterer noen (x)-verdi, x ₀ og noen konstant, C, hvor f (x) er mindre enn eller lik at konstant ganger g (x) for alle x større enn x ₀. 

Men ikke bli skremt vekk av den formelle definisjonen. Hva betyr dette egentlig betyr i mindre teoretisk? Vel, det er i utgangspunktet en måte å analysere hvor fort et program runtime vokser asymptotisk. Det er, som størrelsen på dataen øker mot uendelig, si, du sortere en rekke størrelse 1000 sammenlignet med en rekke størrelse 10. Hvordan vokse runtime på programmet? Tenk deg for eksempel telle antall tegn i en streng den enkleste måten  ved å gå gjennom hele strengen bokstav for bokstav og tilsetning av 1 til en teller for hvert tegn. Denne algoritmen er sagt å kjøre i lineær tid med hensyn til det antall tegn, 'N' i strengen. Kort sagt, det går i O (n). Hvorfor er dette? Vel, ved hjelp av denne tilnærmingen, krevde tid å traversere hele strengen er proporsjonal med antall tegn. Telle antall tegn i en 20-tegnstreng kommer til å ta dobbelt så lang tid som det tar å telle tegnene i en 10-tegns streng, fordi du må se på alle tegnene og hvert tegn tar like mye tid til å se på. Når du øker antall tegn, driftstiden vil øke lineært med input lengde. 

Nå forestille seg hvis du bestemmer deg for at lineær tid, O (n), var bare ikke fort nok for deg? Kanskje du lagrer store strenger, og du ikke har råd til den ekstra tiden det ville ta å traversere alle sine karakterer teller én etter én. Så bestemmer deg for å prøve noe annerledes. Hva om du ville skje med allerede lagre nummeret tegn i strengen, sier i en variabel kalt 'len' tidlig i programmet, før du selv lagret det aller første tegnet i strengen din? Deretter alt du måtte gjøre nå for å finne ut strengen lengde, er å sjekke hva verdien av variabelen er. Du ville ikke trenger å se på selve strengen i det hele tatt, og tilgang til verdien av en variabel som len regnes en asymptotisk konstant tid drift, eller O (1). Hvorfor er dette? Vel, husk hva asymptotisk kompleksitet betyr. Hvordan får runtime endring som størrelsen av dataen vokser? 

Si du prøvde å få antall tegn i en større streng. Vel, ville det ingen rolle hvor stor du gjør streng, enda en million tegn, alt du måtte gjøre for å finne strengens lengde med denne tilnærmingen, er å lese ut verdien av variabelen len, som du allerede har gjort. Input lengde, det vil si lengden av strengen du forsøker å finne, påvirker ikke i det hele tatt hvor raskt programmet kjører. Denne delen av programmet vil kjøre like fort på en en-tegnstreng og tusen-tegnstreng, og det er derfor dette programmet ville bli referert til som kjører i konstant tid med hensyn til inngangen størrelse. 

Selvfølgelig, det er en ulempe. Du tilbringe ekstra lagringsplass på datamaskinen lagring variabelen og den ekstra tiden det tar deg å gjøre selve lagring av variabelen, men poenget står fortsatt, finne ut hvor lenge streng var ikke avhengig av lengden av strengen i det hele tatt. Så, det går i O (1) eller konstant tid. Dette absolutt ikke å bety at koden kjøres i trinn 1, men uansett hvor mange skritt det er, hvis den ikke endrer med størrelsen av inngangene, det er fortsatt asymptotisk konstant som vi representerer som O (1). 

Som du kan sikkert gjette, er det mange forskjellige store O kjøretidsfiler å måle algoritmer med. O (n) ² algoritmer er asymptotisk tregere enn O (n) algoritmer. Det er, som antall elementer (n) vokser, slutt O (n) ² algoritmer vil ta mer tid enn O (n) algoritmer å kjøre. Dette betyr ikke O (n) algoritmer alltid kjøre raskere enn O (n) ² algoritmer, selv i det samme miljøet, på samme maskinvare. Kanskje for liten input størrelser,  O (n) ² algoritmen kan faktisk jobbe raskere, men, til slutt, som input størrelsen øker mot uendelig, O (n) ² algoritme runtime vil til slutt overskygger runtime på O (n) algoritme. Akkurat som alle kvadratisk matematisk funksjon  vil til slutt gå forbi noen lineær funksjon, uansett hvor mye av et hode starte lineær funksjon starter med. Hvis du arbeider med store mengder data, algoritmer som kjører i O (n) ² tid kan virkelig ende opp bremse ned programmet, men for små innspill størrelser, du sannsynligvis vil ikke engang merke til. 

En annen asymptotisk kompleksitet er, logaritmisk tid O (log n). Et eksempel på en algoritme som kjører dette raskt er den klassiske binære søk algoritme, for å finne et element i et allerede sortert liste av elementer. 

Hvis du ikke vet hva binær søk gjør, Jeg skal forklare det for deg veldig raskt. La oss si at du leter etter nummer 3 i denne rekke heltall. Den ser på midten element i matrisen og spør: "Er element jeg vil ha større enn, lik eller mindre enn dette?" Hvis det er lik, så flott. Du fant elementet, og du er ferdig. Hvis den er større, så vet du elementet må være på høyre side av tabellen, og du kan bare se på at det i fremtiden, og hvis det er mindre, så du vet det må være på venstre side. Denne prosessen blir så gjentatt med den mindre størrelse matrise inntil riktig elementet er funnet. 

Denne kraftige algoritmen kutter gitterstørrelse i to med hver operasjon. Så, for å finne et element i en sortert rekke størrelse 8, på de fleste (log ₂ 8), eller 3 av disse operasjonene, sjekke midten element, deretter kutte array i halvparten vil være nødvendig, mens en rekke størrelser som 16 tar (log ₂ 16), eller 4 operasjoner. Det er bare en mer bruk for en doblet størrelse array. Dobling av størrelsen på matrisen øker runtime med kun 1 del av denne koden. Igjen, sjekke midt element i listen, og splitting. Så er det sagt å operere i logaritmisk tid, O (log n). Men vent, du sier, ikke dette avhenger av hvor i listen elementet du leter etter er? Hva om det første elementet du ser på skjer for å være den rette? Deretter tar det bare en operasjon, uansett hvor stor den listen er. 

Vel, det er derfor dataforskere har flere ord for asymptotisk kompleksitet som reflekterer best-case og worst-case forestillinger av en algoritme. Mer riktig, øvre og nedre grenser på runtime. I beste fall for binære søk, er vår element der i midten, og du får den i konstant tid, uansett hvor stor resten av tabellen er. Symbolet som brukes til dette er Ω. Så, er denne algoritmen sagt å kjøre i Ω (1). I beste fall, finner den det elementet raskt, uansett hvor stor matrise er, men i verste fall, det må utføre (log n) split sjekker i matrisen for å finne den rette element. Worst-case øvre grense er referert til med den store "O" som du allerede vet. Så, det er O (log n), men Ω (1). 

En lineær søk, derimot, der du går gjennom hvert element i matrisen å finne det du vil ha, er i beste Ω (1). Igjen, det første elementet du ønsker. Så det spiller ingen rolle hvor stor matrise er. I verste fall er det siste elementet i matrisen. Så må du gå gjennom alle n elementer i matrisen for å finne den, som om du var på utkikk etter en 3. Så, det går i O (n) tid fordi det er proporsjonal med antallet av elementer i matrisen. 

Enda et symbol som brukes er Θ. Dette kan brukes til å beskrive algoritmer hvor de beste og verste tilfeller er de samme. Dette er tilfellet i streng-lengde algoritmer vi snakket om tidligere. Det vil si, hvis vi lagre den i en variabel før vi lagre strengen og få tilgang til den senere i konstant tid. Uansett hvilket nummer Vi lagrer i den variabelen, må vi se på det. Det beste fall er, ser vi på det og finne lengden på strengen. Så Ω (1) eller best-case konstant tid. Det verste tilfellet er, Vi ser på det og finne lengden av strengen. Slik, O (1) eller konstant tid i verste tilfelle. Så, siden den beste tilfelle og verste tilfellene er de samme, Dette kan sies å kjøre i Θ (1) gang. 

Oppsummert har vi gode måter å resonnere om koder effektivitet uten å vite noe om den virkelige verden tid de tar å kjøre, som påvirkes av mange ytre faktorer, inkludert ulike maskinvare, programvare, eller spesifikk av koden din. Også gir det oss å resonnere godt om hva som vil skje når størrelsen av inngangene øker. 

Hvis du kjører i O (n) ² algoritme, eller enda verre, en O (2 ⁿ) algoritme, en av de raskest voksende, vil du virkelig begynne å merke nedgangen når du begynner å arbeide med større mengder data. 

Det er asymptotisk kompleksitet. Takk.