Algoritmer, og hvordan man analyserer deres kompleksitet

Algoritmer er involveret i næsten alle de opgaver, vi udfører på daglig basis. Vi udfører mange af dem på "automatisk" uden selv at indse "hvad" de bruges til eller "hvordan" vi bruger dem. I softwareudvikling er det ikke så anderledes. Men hvad er algoritmer alligevel? Og hvorfor er det vigtigt at analysere deres kompleksitet?

Lad os finde ud af det! :)

Hvad er en algoritme?

Et sæt trin, der er nødvendige for at udføre en opgave.

Computerprogrammer er ikke de eneste ting, der udfører algoritmer, de udføres og implementeres også af os mennesker.

Har du f.eks. Tænkt på den algoritme, der udfører følgende opgaver?

  • Børst dine tænder
  • Tag et bad
  • laver mad
  • Kør til arbejde hjemmefra

I vores daglige udførelse udfører vi en række trin for at udføre mindst en af ​​de nævnte opgaver. Lad os bruge opgaverne til at arbejde hjemmefra som et eksempel. De trin, jeg tager, er dybest set som følger:

  1. Kom ind i min bil
  2. Kør hjem til en ven for at give dem en tur
  3. Kør til kontoret, hvor jeg arbejder
  4. Parker min bil i parkeringshuset

Dette er det sæt trin (algoritme), jeg skal udføre for at fuldføre denne opgave.

Tænk nu på det nødvendige sæt trin, du tager for at udføre den samme opgave. Det er sandsynligt, at de er lidt anderledes end mine. Vores algoritmer kan være forskellige, men vores mål er det samme.

Computerprogrammer er ikke for forskellige: der er en række algoritmer, der kan bruges til at udføre en række opgaver. Ofte bekymrer vi os ikke om, hvad de er, vi bruger dem bare (mig selv inkluderet).

Hvordan skal for eksempel den algoritme, der bruges af Waze og Google Maps, den, der beregner den bedste rute mellem to placeringer, se ud? Hvad med Netflix's algoritme, der foreslår film og serier baseret på det, du har set?

Personligt kunne jeg ikke fortælle dig det. Jeg ved dog, at de er effektive. Og effektivitet er den standard, vi bruger til at analysere en algoritmes kompleksitet.

Hvad er algoritme-kompleksitet?

I computervidenskab refererer algoritme-kompleksitet til, hvor meget tid og plads en algoritme bruger til at udføre en opgave, afhængigt af størrelsen på dens input.

Generelt evalueres algoritmer ud fra deres forbrug af både tid og rum, men jeg vil kun tage fat på tidskompleksiteten i dette indlæg.

Analyse af tidskompleksitet gør det muligt for os at bestemme, hvordan en algoritme vil opføre sig i betragtning af en stigning i dens inputelementer. Vi kan have en idé om den tid det vil tage at behandle 10, 100 eller 1000 elementer.

Og hvorfor er denne analyse vigtig?

  • At bestemme, hvilken algoritme der er mest effektiv;
  • At være i stand til at udvikle mere effektive algoritmer;
  • At være i stand til at analysere, om en algoritmes bibliotek eller endog dets faktiske sprog er effektive.

For at opsummere er effektivitet pointen!

Tidskompleksitet

Den tid det tager for en aktivitet at afslutte.

Vi kan begynde at analysere tiden med Frequency Count-metoden, der dybest set tæller antallet af gange en maskineinstruktion udføres. Hvert trin (instruktion) tildeles en tidsenhed, der starter med 1.

Den tid, algoritmen bruger, udtrykkes af funktionen f (n), hvor n repræsenterer datastørrelsen.

Resultatet af en analyse udtrykkes som følger:

([funktion, der udtrykker tid]) = [Summen af ​​tidsenhederne]

Lad os nu analysere nogle algoritmer for at forstå, hvordan dette fungerer i virkeligheden.

Den første funktion tilføjer to hele tal:

Vi kan se, at for den nævnte opgave udfører den implementerede algoritme kun et enkelt trin: summeringen af ​​to tal. Da vi attribuerer en værdi for hvert trin, er resultatet f (n) = 1.

Lad os se på det næste eksempel, som er en algoritme, der deler et heltal med et andet heltal:

På trods af at det er en matematisk operation, der ligner summation, indeholder algoritmen flere trin, fordi den skal kontrollere, om divisoren er 0; hvis dette er tilfældet, vil divisionen ikke blive realiseret. Da vi i alt har fire trin, og hver af disse tildeles en værdi på 1, er resultatet f (n) = 4.

Den næste algoritme opsummerer alle elementerne i en liste med heltal:

I denne algoritme inkluderer et af trinnene til en instruktion til gentagelse; Dette betyder, at koden inde i for udføres flere gange. Da antallet af henrettelser afhænger af datastørrelsen, attribuerer vi værdien af ​​n som en tidsenhed. Resultatet er f (n) = 2n + 3.

Den næste algoritme tilføjer summen af ​​en liste med summen af ​​en anden liste.

Som et resultat har vi f (n) = 2n² + 2n + 3.

Indtil dette tidspunkt har vi kun set enkle algoritmer, ikke? Forestil dig nu at analysere mere komplekse algoritmer og har brug for at udføre disse beregninger? Ikke meget muligt, er det? Selvom det ser ud til at være det mest passende, er det meget mødeligt og i slutningen af ​​dagen er det ikke værd.

Normalt, når vi analyserer en algoritme, forsøger vi at finde ud af dens adfærd, når der er mange elementer at behandle. Det er i disse situationer, vi har brug for at finde den dominerende periode for summen af ​​tidsenhederne.

For eksempel, hvad er den dominerende udtryk for summen af ​​den tredje algoritme?

f (n) = 2n + 3

I dette tilfælde er det dominerende udtryk i 2 * n, og jeg vil forklare hvorfor!

I enhver situation, hvor n er større end 1 (n> 1), vil produktet (resultatet af multiplikation) allerede være værd mere end den anden periode af summen.

Test noget: erstatt n med ethvert heltal større end 1, og udfør multiplikationen.

Hvad med den dominerende udtryk for summen af ​​den sidste algoritme?

f (n) = 2n² + 2n + 3

I dette tilfælde er det dominerende udtryk 2 * n², fordi når n> 1, vil produktet altid være større end det andet og tredje udtryk for summen. Gå videre, test det!

Ergo, der er en mere almindelig måde, så at sige, at analysere kompleksiteten af ​​algoritmer, hvor konstanter og mindre betydningsfulde udtryk ses bort fra. Denne metode kaldes asymptotisk kompleksitet.

Det er her Order of Complexity kommer i spil, også kendt som Notation-O eller Big-O.

Big-O notation

Bruges til at klassificere en algoritme i betragtning af vækstraten for operationer, når antallet af behandlede elementer vokser.

Big-O notation definerer også en funktion, der udtrykker en algoritmes tidskompleksitet. Til dette formål bruges n som en funktion af bogstavet O.

De mest almindelige klasser er:

  • O (1) - Konstant, antallet af operationer stiger ikke, når antallet af elementer stiger
  • O (log n) - Logaritmisk, antallet af operationer er mindre end antallet af elementer
  • O (n) - Lineært øges antallet af operationer proportionalt med antallet af elementer
  • O (n²) Kvadratisk, vil antallet af operationer være større end antallet af elementer
  • O (2 ^ n) - Eksponent, antallet af operationer stiger hurtigt sammenlignet med antallet af elementer
  • O (n!) - Faktoralt stiger antallet af operationer meget, meget hurtigt, selv for et lille antal elementer

Nedenfor har vi en grafik, der illustrerer vækstraten for operationer x antallet af elementer:

Grafikken er klassificeret som følger:

  • Rød zone er forfærdeligt, undgå det!
  • Orange zone er dårlig, undgå det også!
  • Gul zone er fair, rimelig!
  • Lysgrøn zone er god, cool!
  • Mørkegrøn zone er fremragende, tillykke!

Nu skal vi bruge Big-O-notation til at kategorisere de algoritmer, der tidligere blev nævnt, og altid bruge deres fremherskende udtryk til at guide os.

Den første algoritme resulterede i f (n) = 1; hvilket betyder, at uafhængigt af en stigning i elementer, udfører algoritmen kun en operation. Således kan vi klassificere algoritmen som konstant - O (1).

Den anden algoritme resulterede i f (n) = 4; hvilket betyder, at uafhængigt af en stigning i elementer, vil algoritmen udføre fire operationer. Således kan vi også klassificere denne algoritme som Konstant - O (1).

Resultatet af den tredje algoritme var f (n) = 2n + 3; hvilket betyder, at antallet af operationer vil vokse proportionalt med antallet af elementer i betragtning af, hvordan n fungerer som en variabel i denne funktion. Således kan vi definere denne algoritme som Lineær - O (n).

Resultatet af den sidste algoritme resulterede i f (n) = 2n² + 2n + 3, hvilket betyder, at antallet af operationer vil stige mere end antallet af elementer. I dette tilfælde fungerer n også som en variabel, men den hæves til den anden effekt (kvadratisk). Således kan vi definere denne algoritme som Kvadratisk - O (n²).

Tabellen nedenfor illustrerer væksten i antallet af operationer, da den vedrører væksten i antallet af elementer.

Bemærk, at 16 elementer i en eksponentiel algoritme ville resultere i mindst 65.5536 operationer. Temmelig foruroligende, ikke?

Generelt er analyseprocessen den samme, som vi har gjort: at tælle antallet af trin og identificere det dominerende udtryk.

Nogle tendenser vi kan observere:

  • Algoritmer, der ikke har en repetitionssløjfe, har en tendens til at være Konstant - O (1)
  • Algoritmer, der har repetitionssløjfer, så længe de ikke er indlejret, har en tendens til at være lineære - O (n)
  • Algoritmer, der har to indlejrede repetitionssløjfer, har tendens til at være kvadratiske - O (n²)
  • Direkte adgang til indekset for en matrix er normalt O (1) (konstant)
  • Listeudvidelsesmetoder er i gennemsnit O (n). For eksempel: enhver, sum og filter.
  • Sorteringsalgoritmer som Bubble Sort, Insertion Sort og Selection Sort er normalt O (n²).

At vide, hvordan vi klassificerer algoritmer, giver os kapacitet til at bedømme en algoritmes effektivitet eller ineffektivitet. Vi kan selvfølgelig ikke måle dens nøjagtige køretid i sekunder, minutter eller timer. For at gøre dette skal det udføres, måles og ændres i overensstemmelse hermed. Forestil dig at gøre dette for algoritmer, der tager timer eller endda dage at køre? Ikke en chance!

Jeg håber, at jeg har opfyldt målet med dette indlæg, som var at give et overblik over algoritmer og deres analyse ved hjælp af frekvensantal og Big-O-metoder.

Jeg har efterladt nogle referencer nedenfor som yderligere læsestof!

Referencer:

Vídeos 1 til 1.7

Vil du bringe innovation til lånemarkedet gennem teknologi? Vi leder altid efter nye mennesker til at blive medlem af vores besætning!

Tjek vores åbninger her.