[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.