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