[Powered by Google Translate] Du har säkert hört talas om en snabb eller effektiv algoritm för att utföra din uppgift, men vad betyder det för en algoritm för att vara snabb eller effektiv? Tja, det talar inte om en mätning i realtid, Liksom sekunder eller minuter. Detta beror på att maskinvara och programvara varierar kraftigt. Mitt program kan köra långsammare än din, eftersom jag kör det på en äldre dator, eller för att jag råkar vara spela ett online videospel Samtidigt, vilket hogging hela mitt minne, eller jag kanske köra mitt program genom olika programvaror som kommunicerar med maskinen olika vid en låg nivå. Det är som att jämföra äpplen och apelsiner. Bara för att min långsammare dator tar längre än din att ge tillbaka ett svar betyder inte att du har desto mer effektiv algoritm. 

Så, eftersom vi inte direkt kan jämföra drifttider av program i sekunder eller minuter, Hur jämför vi 2 olika algoritmer oavsett hårdvara eller mjukvara miljö? För att skapa ett mer enhetligt sätt att mäta algoritmisk effektivitet, datavetare och matematiker har utarbetat koncept för att mäta det asymptotiska komplexiteten av ett program och en notation som kallas "Big Ohnotation" för att beskriva detta. Den formella definitionen är att en funktion f (x) körs i storleksordningen av g (x) om det finns någon (x) värde, x ₀ och någon konstant, C, för vilket f (x) är mindre än eller lika med att konstant gånger g (x) för alla x större än x ₀. 

Men inte vara rädd bort av den formella definitionen. Vad innebär det egentligen i mindre teoretiskt? Tja, det är i grunden ett sätt att analysera hur snabbt ett programs körning växer asymptotiskt. Det är, som storleken på dina insatser ökar mot oändligheten, säger, du sorterar en rad storlek 1000 jämfört med en rad storlek 10. Hur växer runtime för ditt program? Tänk dig till exempel att räkna antalet tecken i en sträng det enklaste sättet  genom att gå igenom hela strängen bokstav för bokstav och tillsätta 1 till en räknare för varje tecken. Denna algoritm sägs gå i linjär tid med avseende på antalet tecken, "N" i strängen. Kort sagt, kör det i O (n). Varför är det här? Nåväl, med denna metod, krävs tid att korsa hela strängen är proportionell mot antalet tecken. Räkna antalet tecken i en 20-teckensträng kommer att ta dubbelt så lång tid som det tar att räkna tecknen i en 10-teckensträng, eftersom du måste titta på alla tecken och varje tecken tar lika lång tid att titta på. När du ökar antalet tecken, körningen ökar linjärt med den ingående längd. 

Nu, tänk om du bestämmer att linjär tid, O (n), var helt enkelt inte snabb nog för dig? Kanske du lagra stora strängar, och du inte har råd den extra tid det skulle ta att korsa alla sina karaktärer räkna en-för-en. Så bestämmer dig att prova något annat. Vad händer om du skulle hända redan lagra antalet tecken i strängen, säger i en variabel som heter "Len" tidigt i programmet, innan du lagras även den allra första tecknet i strängen? Sedan allt du måste göra nu för att ta reda på stränglängd, är kolla vad värdet på variabeln är. Du skulle inte behöva titta på strängen själv alls, och åtkomst till värdet för en variabel som len anses en asymptotiskt konstant tid drift, eller O (1). Varför är det här? Tja, kom ihåg vad asymptotisk komplexitet innebär. Hur runtime förändring som storleken av dina ingångar växer? 

Säg att du försökte få antalet tecken i en större sträng. Tja, det skulle ingen roll hur stor du gör strängen, även en miljon tecken, allt du skulle behöva göra för att hitta strängen längd med detta tillvägagångssätt, är att läsa ut värdet på variabeln len, som ni redan gjort. Ingången längd, dvs längden på strängen du försöker hitta, påverkar inte alls hur snabbt ditt program körs. Denna del av programmet skulle gå lika snabbt på en en-teckensträng och tusen-teckensträng, och det är därför detta program skulle kallas körs i konstant tid med avseende på ingående storlek. 

Naturligtvis finns det en nackdel. Du tillbringar extra minnesutrymme på datorn lagra variabeln och den extra tid det tar att göra själva lagringen av variabeln, men poängen står stilla, ta reda på hur lång tid din sträng var beror inte på längden av strängen alls. Så kör det i O (1) eller konstant tid. Detta absolut inte behöver betyda att koden körs i 1 steg, men oavsett hur många steg det är, om det inte förändras med storleken av insignalerna, det är fortfarande asymptotiskt konstant som vi representerar som O (1). 

Som ni säkert kan gissa, det finns många olika Big O drifttider för att mäta algoritmer med. O (n) ² algoritmer är asymptotiskt långsammare än O (n) algoritmer. Det är, eftersom antalet element (n) växer, småningom O (n) ² algoritmer tar längre tid än O (n) algoritmer för att köra. Detta betyder inte O (n) algoritmer alltid springa snabbare än O (n) ² algoritmer, även i samma miljö, på samma hårdvara. Kanske för små ingång storlekar,  O (n) ² algoritm kan faktiskt arbeta snabbare, men så småningom, som ingång storlek ökar mot oändligheten, O (n) ² algoritmens runtime kommer så småningom överskugga runtime av O (n) algoritm. Precis som alla kvadratisk matematisk funktion  kommer så småningom köra någon linjär funktion, oavsett hur mycket ett försprång den linjära funktionen börjar med. Om du arbetar med stora mängder data, algoritmer som körs i O (n) ² tid kan verkligen hamna saktar ner ditt program, men för små inmatade storlekar, du förmodligen inte ens märker. 

Annan asymptotiska komplexitet är, logaritmisk tid, O (log n). Ett exempel på en algoritm som kör detta snabbt är den klassiska binära sökalgoritm, för att finna ett element i en redan sorterade listan över element. 

Om du inte vet vad binär sökning gör, Jag ska förklara det för dig riktigt snabbt. Låt oss säga att du letar efter siffran 3 i denna grupp av heltal. Det ser i mitten element i arrayen och frågar, "Är elementet jag vill ha mer än, lika med eller mindre än detta?" Om det är lika så bra. Du hittade elementet, och du är klar. Om det är större, då vet du att elementet måste vara i den högra sidan av gruppen, och du kan bara titta på det i framtiden, och om det är mindre, så du vet att det måste vara på vänster sida. Denna process upprepas sedan med den mindre storlek matris tills korrekt elementet hittas. 

Denna kraftfulla algoritm klipper matrisstorlek i halv med varje operation. Så, för att finna ett element i en sorterad array med storlek 8, högst (log ₂ 8), eller 3 av dessa operationer, kontrollera mellersta elementet, sedan skära arrayen i halv kommer att krävas, medan en rad storlek 16 tar (log ₂ 16), eller 4 operationer. Det är bara 1 mer drift under en dubbelt storlek array. En fördubbling av storleken på matrisen ökar runtime med endast 1 bit av denna kod. Återigen, kontrollera den mellersta delen av listan, sedan dela. Så är det sagt att arbeta i logaritmisk tid, O (log n). Men vänta, du säger, inte detta beror på var i listan elementet du letar efter är? Vad händer om det första elementet du tittar på råkar vara den rätta? Sedan tar det bara 1 operation, oavsett hur stor listan är. 

Tja, det är därför datavetare har fler villkor för asymptotisk komplexitet som speglar bästa fall och värsta föreställningar av en algoritm. Mer korrekt, de övre och nedre gränser på körningen. I bästa fall för binär sökning, är vår del rätt där i mitten, och du får det i konstant tid, oavsett hur stor resten av matrisen är. Den symbol som används för detta är Ω. Så, denna algoritm sägs köra i Ω (1). I bästa fall, finner det elementet snabbt, oavsett hur stor gruppen är, men i värsta fall, det måste ha (log n) delade kontroller i matrisen för att hitta rätt element. Värsta övre gräns kallas med den stora "O" att du redan vet. Så är det O (log n), men Ω (1). 

En linjär sökning, däremot, där du går igenom varje element i arrayen att hitta det du vill, är i bästa Ω (1). Återigen det första elementet som du vill. Så det spelar ingen roll hur stor gruppen är. I värsta fall är det det sista elementet i arrayen. Så måste du gå igenom alla n element i arrayen att hitta den, som om du letade efter en 3. Så kör det i O (n) tid eftersom det är proportionellt mot antalet element i arrayen. 

En mer symbol som används är Θ. Detta kan användas för att beskriva algoritmer där de bästa och sämsta fall är desamma. Detta är fallet i strängen längd algoritmer vi talat om tidigare. Det är, om vi förvara den i en variabel innan Vi lagrar strängen och komma åt den senare konstant tid. Oavsett vilket nummer vi lagrar i den variabeln, vi måste titta på det. I bästa fall är, tittar vi på det och hitta längden på strängen. Så Ω (1) eller bästa fall konstant tid. Det värsta fallet är, vi tittar på det och hitta längden på strängen. Så, O (1) eller konstant tid i värsta fall. Så, eftersom det bästa fall och värsta fall är desamma, detta kan sägas att köras i Θ (1) tid. 

Sammanfattningsvis har vi goda möjligheter att resonera om koder effektivitet utan att veta något om den verkliga tid de tar att köra, som påverkas av många yttre faktorer, inklusive olika hårdvara, mjukvara, eller detaljerna i din kod. Dessutom ger det oss att resonera väl om vad som kommer att hända när storleken på ingångarna ökar. 

Om du kör i O (n) ² algoritm, eller ännu värre, en O (2 ⁿ) algoritm, en av de snabbast växande typerna, du verkligen börja märka avmattningen När du börjar arbeta med större datamängder. 

Det är asymptotisk komplexitet. Tack.