[Powered by Google Translate] Du har sikkert hørt folk tale om en hurtig eller effektiv algoritme
for at gennemføre netop din opgave,
men hvad betyder det for en algoritme til at være hurtig eller effektiv?
Tja, det er ikke tale om en måling i realtid,
lignende sekunder eller minutter.
Dette skyldes computerhardware
og software varierer drastisk.
Mit program kan køre langsommere end dit,
fordi jeg kører det på en ældre computer,
eller fordi jeg tilfældigvis skal spille en online video game
på samme tid, som er hogging al min hukommelse,
eller jeg kan køre mit program gennem forskellige software
som kommunikerer med maskinen forskelligt på et lavt niveau.
Det er som at sammenligne æbler og appelsiner.
Bare fordi min langsommere computer tager længere tid
end din at give tilbage et svar
betyder ikke, du har, jo mere effektiv algoritme.
>> Så da vi ikke direkte kan sammenligne de runtime af programmer
i sekunder eller minutter,
hvordan kan vi sammenligne 2 forskellige algoritmer
uanset deres hardware eller software miljø?
At skabe et mere ensartet måde at måle algoritmisk effektivitet,
dataloger og matematikere har udtænkt
koncepter til måling af asymptotiske kompleksitet et program
og en notation kaldet 'Big Ohnotation'
til beskrivelse af dette.
Den formelle definition er, at en funktion f (x)
kører i størrelsesordenen g (x)
Hvis der findes en (x) værdi, x ₀ og
eller anden konstant, C, for hvilke
f (x) er mindre end eller lig med
at konstant gange g (x)
for alle x større end x ₀.
>> Men du skal ikke blive skræmt væk af den formelle definition.
Hvad betyder dette egentlig betyder i mindre teoretiske termer?
Tja, det er dybest set en måde at analysere
hvor hurtigt et program runtime vokser asymptotisk.
Det er, som størrelsen på dine input øges mod uendeligheden,
sige, du sortering et array af størrelse 1000 i forhold til et array af størrelse 10.
Hvordan runtime af dit program vokse?
For eksempel forestille sig at tælle antallet af tegn
i en snor den simpleste måde
ved at gå gennem hele strengen
brev-by-brev og lægge 1 til en tæller for hver karakter.
Denne algoritme siges at køre i lineær tid
med hensyn til antallet af tegn,
'N' i strengen.
Kort sagt, kører det i O (n).
Hvorfor er det?
Nå, ved hjælp af denne metode, den nødvendige tid
at krydse hele strengen
er proportional med det antal tegn.
Tælle antallet af tegn i en 20-tegnstreng
vil tage dobbelt så lang som det tager
at tælle tegnene i en 10-tegnstreng,
fordi du er nødt til at se på alle tegn
og hver karakter tager den samme mængde tid til at se på.
Når du øger antallet af tegn,
runtime vil øges lineært med input længde.
>> Nu, tænk hvis du beslutter dig for at lineær tid,
O (n), var bare ikke hurtig nok for dig?
Måske er du gemme enorme strenge,
og du kan ikke råd til den ekstra tid, det ville tage
at krydse alle deres karakterer tæller én efter én.
Så du beslutter dig for at prøve noget andet.
Hvad hvis du ville der ske med allerede gemme antallet af tegn
i strengen, siger, i en variabel kaldet 'len'
tidligt i programmet,
før du selv gemt det allerførste tegn i din streng?
Så alt hvad du nødt til at gøre nu for at finde ud af strengen længde,
er kontrollere, hvad værdien af ​​variablen er.
Du ville ikke have til at se på selve strengen på alle,
og adgang til værdien af ​​en variabel ligesom len anses
en asymptotisk konstant tid drift,
eller O (1).
Hvorfor er det? Nå, huske, hvad asymptotisk kompleksitet betyder.
Hvordan runtime ændring som den størrelse
af dine input vokser?
>> Sig, at du forsøgte at få antallet af tegn i en større streng.
Nå, ville det ikke ligegyldigt hvor stor du gør strengen,
selv en million tegn,
alt hvad du nødt til at gøre for at finde strengen længde med denne tilgang,
at læse værdien af ​​den variable len,
som du allerede har gjort.
Input længde, det vil sige længden af ​​strengen man prøver at finde,
påvirker ikke på alle, hvor hurtigt dit program kører.
Denne del af dit program ville køre lige så hurtigt på en en-tegnstreng
og tusind-tegnstreng,
og det er derfor dette program vil blive omtalt som kører i konstant tid
med hensyn til input-størrelse.
>> Selvfølgelig er der en ulempe.
Du tilbringer ekstra hukommelse på din computer
lagring af variable
og den ekstra tid det tager dig
at gøre det egentlige lagring af variable,
men pointen stadig står,
finde ud af, hvor længe din streng var
ikke afhænger af længden af ​​strengen overhovedet.
Så det kører i O (1) eller konstant tid.
Det betyder bestemt ikke at betyde
at din kode kører i 1 trin,
men uanset hvor mange skridt det er,
hvis det ikke ændres med størrelsen af ​​de input,
det er stadig asymptotisk konstant, som vi repræsenterer som O (1).
>> Som du sikkert kan gætte,
der er mange forskellige store O funktionstider at måle algoritmer med.
O (n) ² algoritmer er asymptotisk langsommere end O (n) algoritmer.
Det vil sige, idet antallet af elementer (n) vokser,
til sidst O (n) ² algoritmer vil tage længere tid
end O (n) algoritmer til at køre.
Det betyder ikke O (n) algoritmer altid køre hurtigere
end O (n) ² algoritmer, selv i det samme miljø
på den samme hardware.
Måske til små input størrelser,
O (n) ² algoritme kan faktisk arbejde hurtigere,
men i sidste ende, som input størrelse stiger
mod uendeligheden, O (n) ² algoritmen runtime
i sidste ende vil overskygge den runtime af O (n) algoritme.
Ligesom enhver kvadratisk matematisk funktion
sidste ende vil overtage en lineær funktion,
uanset hvor meget af et forspring den lineære funktion starter med.
Hvis du arbejder med store mængder data,
algoritmer, der kører i O (n) ² tid virkelig kan ende med at bremse dit program,
men for små input størrelser,
De vil sandsynligvis ikke engang mærke til det.
>> En anden asymptotiske kompleksitet er,
logaritmisk tid, O (log n).
Et eksempel på en algoritme, der kører denne hurtigt
er den klassiske binære søgealgoritme,
for at finde et element i en allerede sorteret liste over bestanddele.
>> Hvis du ikke ved, hvad binær søgning gør,
Jeg vil forklare det for dig virkelig hurtigt.
Lad os sige, du leder efter tallet 3
i denne række af heltal.
Det ser på den midterste element i arrayet
og spørger: "Er det element jeg ønsker større end, lig med eller mindre end dette?"
Hvis det er lige, så stor. Du fandt det element, og du er færdig.
Hvis det er større, så du kender element
skal være i højre side af opstillingen,
og du kan kun se på det i fremtiden,
og hvis det er mindre, så du ved, det må være i venstre side.
Denne proces gentages derefter med den mindre størrelse matrix
indtil det korrekte element er fundet.
>> Denne kraftfulde algoritme skærer array-størrelse i halve med hver operation.
Så for at finde et element i en sorteret array af størrelse 8,
højst (log ₂ 8),
eller 3 af disse transaktioner,
kontrollere den midterste element, så skære arrayet i halvdelen vil være påkrævet,
henviser til et array af størrelse 16 tager (log ₂ 16),
eller 4 operationer.
Det er kun 1 mere operation for en dobbelt-størrelse array.
Fordobling af størrelsen af ​​grupperingen
øger runtime ved kun 1 bid af denne kode.
Igen, kontrol den midterste element i listen, så opdelingen.
Så er det sagt at operere i logaritmisk tid,
O (log n).
Men vent, du siger,
ikke dette afhænger af, hvor på listen det element, du leder efter, er?
Hvad hvis det første element, du ser på sker for at være den rigtige?
Så det tager kun 1 operation,
uanset hvor stor listen er.
>> Nå, det er derfor dataloger har flere vilkår
for asymptotiske kompleksitet, der afspejler den bedst tænkelige
og værst tænkelige præstationer af en algoritme.
Mere korrekt, de øvre og nedre grænser
på runtime.
I bedste fald for binær søgning, er vores element
lige der i midten,
og du får det i konstant tid,
uanset hvor stor resten af ​​arrayet er.
Symbolet anvendes til dette er Ω.
Så bliver denne algoritme siges at køre i Ω (1).
I bedste fald finder det elementet hurtigt,
uanset hvor stor array er,
men i værste fald,
den skal udføre (log n) delte checks
af arrayet at finde den rigtige element.
Worst-case øvre grænser benævnes med det store "O", som du allerede kender.
Så det er O (log n), men Ω (1).
>> En lineær søgning derimod
hvor man går gennem alle elementer i arrayet
at finde det, du ønsker,
er i bedste Ω (1).
Igen det første element, du ønsker.
Så er det ligegyldigt, hvor stor array er.
I værste fald er det det sidste element i array.
Så du er nødt til at gå gennem alle n elementer i arrayet for at finde det,
ligesom hvis du var på udkig efter en 3.
Så det kører i O (n) tid
fordi det er proportional med antallet af elementer i array.
>> En mere anvendte symbol er Θ.
Dette kan bruges til at beskrive algoritmer, hvor de bedste og værste tilfælde
er de samme.
Dette er tilfældet i streng-længde algoritmer, vi talte om tidligere.
Det vil sige, hvis vi gemme det i en variabel, før
vi opbevarer strengen og få adgang til det senere i konstant tid.
Ligegyldigt hvad nummer
vi lagring i denne variabel, vil vi nødt til at se på det.
Den bedste fald er, at vi ser på det
og finde længden af ​​strengen.
Så Ω (1) eller best-case konstant tid.
Det værste tilfælde er,
vi ser på det, og finde længden af ​​strengen.
Så, O (1) eller konstant tid i værste fald.
Så da bedste fald og værste tilfælde er de samme,
Dette kan siges at køre i Θ (1) tid.
>> Sammenfattende har vi gode måder at ræsonnere om koder effektivitet
uden at vide noget om den virkelige verden tid de tager at køre,
der er påvirket af mange eksterne faktorer,
herunder forskellige hardware, software,
eller detaljerne i din kode.
Også, det giver os mulighed for at ræsonnere sig om, hvad der vil ske
når størrelsen af ​​input stiger.
>> Hvis du kører i O (n) ² algoritme,
eller værre, en O (2 ⁿ) algoritme,
en af ​​de hurtigst voksende typer,
vil du virkelig begynde at lægge mærke afmatningen
når du begynder at arbejde med større mængder af data.
>> Det er asymptotisk kompleksitet. Tak.