En introduktion til algoritmernes tidskompleksitet

Inden for datalogi er analyse af algoritmer en meget vigtig del. Det er vigtigt at finde den mest effektive algoritme til løsning af et problem. Det er muligt at have mange algoritmer til at løse et problem, men udfordringen her er at vælge den mest effektive.

Nu er pointen, hvordan kan vi genkende den mest effektive algoritme, hvis vi har et sæt forskellige algoritmer? Her opstår begrebet rum og tidskompleksitet af algoritmer. Rum- og tidskompleksitet fungerer som en måleskala for algoritmer. Vi sammenligner algoritmerne på baggrund af deres plads (mængde hukommelse) og tidskompleksitet (antal operationer).

Den samlede mængde af computerens hukommelse, der bruges af en algoritme, når den udføres, er pladsens kompleksitet af denne algoritme. Vi diskuterer ikke rumkompleksitet i denne artikel (for at gøre denne artikel lidt mindre).

Tidskompleksitet

Så tidskompleksiteten er antallet af operationer, som en algoritme udfører for at fuldføre sin opgave (i betragtning af at hver operation tager den samme tid). Algoritmen, der udfører opgaven i det mindste antal operationer, betragtes som den mest effektive med hensyn til tidskompleksitet. Imidlertid er plads og tidskompleksitet også påvirket af faktorer som dit operativsystem og hardware, men vi inkluderer dem ikke i denne diskussion.

For at forstå tidskompleksiteten tager vi et eksempel, hvor vi sammenligner to forskellige algoritmer, der bruges til at løse et bestemt problem.

Problemet er at søge. Vi er nødt til at søge efter et element i en matrix (i dette problem antager vi, at arrayet er sorteret i stigende rækkefølge). For at løse dette problem har vi to algoritmer:

1. Lineær søgning.

2. Binær søgning.

Lad os sige, at arrayet indeholder ti elementer, og at vi skal finde tallet ti i arrayet.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

Lineær søgealgoritme sammenligner hvert element i arrayet med search_digit . Når det finder search_digit i arrayet, returneres det true .

Lad os nu tælle antallet af operationer, det udfører. Her er svaret 10 (da det sammenligner hvert element i arrayet). Så, lineær søgning bruger ti operationer til at finde det givne element (disse er det maksimale antal operationer for dette array; i tilfælde af lineær søgning er dette også kendt som det værste tilfælde af en algoritme).

Generelt vil lineær søgning tage n antal operationer i værste fald (hvor n er størrelsen på arrayet).

Lad os undersøge binær søgealgoritmen til denne sag.

Binær søgning kan let forstås ved dette eksempel:

Kilde: Learneroo

Hvis vi prøver at anvende denne logik på vores problem, sammenligner vi først search_digit med det midterste element i arrayet, det vil sige 5. Nu da 5 er mindre end 10, så begynder vi at lede efter search_digit i array-elementerne større end 5, på samme måde, indtil vi får det ønskede element 10.

Prøv nu at tælle antallet af operationer, som binær søgning tog for at finde det ønskede element. Det tog cirka fire operationer. Dette var det værste tilfælde for binær søgning. Dette viser, at der er en logaritmisk relation mellem antallet af udførte operationer og den samlede størrelse af arrayet.

antal operationer = log (10) = 4 (ca.)

til base 2

Vi kan generalisere dette resultat til binær søgning som:

For en matrix af størrelse n er antallet af operationer, der udføres af den binære søgning: log (n)

The Big O Notation

I ovenstående udsagn så vi , at lineær søgning for en matrix af størrelse n udfører n- operationer for at fuldføre søgningen. På den anden side udførte binær søgning log (n) antal operationer (begge i deres værste tilfælde). Vi kan repræsentere dette som en graf ( x-akse : antal elementer, y-akse : antal operationer).

Kilde: Techtud

Det fremgår klart af figuren, at den hastighed, hvormed kompleksiteten stiger for lineær søgning, er meget hurtigere end for binær søgning.

Når vi analyserer en algoritme, bruger vi en notation til at repræsentere dens tidskompleksitet, og at notationen er Big O-notation.

For eksempel: tidskompleksitet for lineær søgning kan repræsenteres som O (n) og O (log n) til Binær søgning (hvor, n og log (n) er antallet af operationer).

Tidskompleksiteten eller Big O-notationerne for nogle populære algoritmer er angivet nedenfor:

  1. Binær søgning: O (log n)
  2. Lineær søgning: O (n)
  3. Hurtig sortering: O (n * log n)
  4. Valg Sort: O (n * n)
  5. Rejsende sælger: O (n!)

Konklusion

Jeg sætter stor pris på din indsats, hvis du stadig læser denne artikel. Nu skal du tænke - hvorfor er tidskompleksitet så vigtigt at forstå?

Vi ved, at forskellen mellem antallet af operationer, der udføres ved binær søgning og lineær søgning, ikke er så stor for et lille antal elementer (f.eks. 10). Men i den virkelige verden beskæftiger vi os mest med problemer, der har store klumper af data.

For eksempel, hvis vi har 4 milliarder elementer at søge efter, vil lineær søgning i værste fald tage 4 milliarder operationer for at fuldføre sin opgave. Binær søgning vil fuldføre denne opgave på kun 32 operationer. Det er en stor forskel. Lad os nu antage, at hvis en operation tager 1 ms til afslutning, tager binær søgning kun 32 ms, mens lineær søgning tager 4 milliarder ms (det vil sige ca. 46 dage). Det er en væsentlig forskel.

Dette er grunden til at studere tidskompleksitet bliver vigtig, når det kommer til så store mængder data.

Ressourcer

Grokking algoritmer - af Aditya Y Bhargava

Introduktion til Big O notation og Time Complexity - af CS Dojo