Kompleksiteten af ​​enkle algoritmer og datastrukturer i JS

I den forrige artikel "Et skridt mod databehandling som videnskab: Enkle algoritmer og datastrukturer i JS" diskuterede vi enkle algoritmer (lineære & binære søgninger; boble-, selektions- og indsættelsessorter) & datastrukturer (array & nøgleværdiparede objekter ). Her fortsætter jeg med begrebet kompleksitet og dets anvendelse på disse algoritmer og datastrukturer.

Kompleksitet

Kompleksitet er en faktor involveret i en kompleks proces. Med hensyn til algoritmer og datastrukturer kan dette være den tid eller det rum (hvilket betyder computerhukommelse), der kræves for at udføre en bestemt opgave (søgning, sortering eller adgang til data) på en given datastruktur. Effektiviteten ved at udføre en opgave afhænger af antallet af operationer, der kræves for at udføre en opgave.

At tage affaldet ud kan kræve 3 trin (at binde en affaldspose, bringe den ud og smide den i en losseplads). Det kan være simpelt at tage affaldet ud, men hvis du tager affaldet ud efter en lang uges renovering, kan du muligvis ikke være i stand til at fuldføre opgaven på grund af mangel på plads i skraldespanden.

Støvsugning af et rum kan kræve mange gentagne trin (tænde det, feje vakuumhovedet gentagne gange over et gulv og slukke det). Jo større et rum, jo ​​flere gange bliver du nødt til at feje et vakuumhoved over gulvet. Jo længere tid det tager at støvsuge rummet , jo længere tid .

Så der er et direkte årsagsforhold mellem antallet af udførte operationer og antallet af elementer, der udføres på. At have en masse affald (elementer) kræver, at det tages ud mange gange. Dette kan føre til et problem med rumkompleksitet . At have en masse firkantede optagelser (elementer) kræver, at man fejer et vakuumhoved over et gulv mange gange. Dette kan føre til et problem med tidskompleksitet .

Uanset om du tager affaldet eller støvsuger et rum , kan du sige, at antallet af operationer ( O ) stiger nøjagtigt med antallet af elementer ( n ) . Hvis jeg har 1 affaldspose, skal jeg tage affaldet ud en gang. Hvis jeg havde to affaldsposer, skal jeg udføre den samme opgave to gange, forudsat at du fysisk ikke kan løfte mere end en pose ad gangen. Så Big-O af disse gøremål er O = n eller O = funktion (n) eller O (n) . Dette er en lineær kompleksitet (en lige linje med 1 operation: 1 elementkorrespondance). Så 30 operationer udføres på 30 elementer (gul linje i grafen).

Dette svarer til hvad der sker, når man overvejer algoritmer og datastrukturer.

Søgninger

Lineær søgning

Det bedste tilfælde for at søge efter en vare på en ordnet liste, den ene efter den anden, er en konstant O (1) , forudsat at den er den første vare på din liste. Så hvis den vare, du søger efter, altid vises først, uanset din listestørrelse, finder du din vare på et øjeblik. Kompleksiteten i din søgning er konstant med listen størrelse. Den gennemsnitlige til det værste tilfælde af denne form for søgning er en lineær kompleksitet eller O (n). Med andre ord,for n varer skal jeg se n gange, inden jeg finder min vare, deraf lineær søgning.

Binær søgning

For en binær søgning er det bedste tilfælde O (1), hvilket betyder, at elementet i din søgning er placeret i midtpunktet. Det værste og gennemsnitlige tilfælde er logbase 2 på n eller:

Logaritme eller log er en måde at udtrykke en eksponent for en given base. Så hvis der var 16 elementer (n = 16), ville det i værste fald tage 4 trin for at finde tallet 15 (eksponent = 4).

Eller simpelthen: O (log n)

Sorterer

Boble

I boblesortering sammenlignes hvert element med resten af ​​samlingen for at bestemme den højeste værdi, der skal bobles op. Af denne grund er dens kompleksitet i gennemsnit til værste tilfælde O (n²) . Tænk en løkke indlejret i en anden sløjfe.

Så for hvert emne sammenligner du det med resten af ​​din samling. Dette svarer til 16 sammenligninger (eller operationer) for 4 elementer (4² = 16). Det bedste tilfælde er, hvis din samling næsten er sorteret, bortset fra en enkelt vare. Dette ville udgøre en enkelt sammenligningsrunde. Det vil sige, at der kræves fire sammenligninger for at boble et medlem af en samling med fire varer, hvilket er en kompleksitet af O (n) .

Udvælgelse

I modsætning til boblesortering vælger markeringssortering den laveste værdi i stedet for at boble den højeste værdi op for at bytte den til de tidligste positioner. Men fordi det kræver sammenligning af hvert element med resten af ​​samlingen, har det også en kompleksitet på O (n²) .

Indskud

I modsætning til de boblen & udvælgelse sorterer , indsættelsessortering indsætter elementet i sin korrekte position. Men ligesom de foregående sorter kræver dette også at sammenligne hvert emne med resten af ​​samlingen, og derfor har det gennemsnit til værste fald kompleksitet på O (n²) . Ligesom boblesorteringen , hvis der kun er et element tilbage at sortere, kræver det kun en enkelt sammenligningsrunde for at indsætte elementet i dets korrekte position. Det vil sige, det har den bedste sag kompleksitet af O (n) .

Datastrukturer

Arrays

Da det tager et enkelt trin at få adgang til et element i et array via dets indeks eller tilføje / fjerne et element i slutningen af ​​et array, er kompleksiteten for at få adgang til , skubbe eller poppe en værdi i en array O (1) . Mens linjær søgning gennem en matrix via dens indeks, som set før, har en kompleksitet på O (n) .

Også, fordi et skift eller fjern skift af en værdi til eller fra forsiden af et array kræver Reindeksering hvert element, der følger det (dvs. fjerne et element ved indeks 0 kræver ommærkning element ved indeks 1 som indeks 0, og så videre), har de en kompleksitet af O (n) . Ommærkning gennemføres fra start til slutning af arrayet.

Nøgle - Værdiparede objekter

Adgang til , indsættelse eller fjernelse af en værdi ved hjælp af en nøgle er øjeblikkelig, og så har de en kompleksitet på O (1) . At søge gennem hver “indskudsboks” efter et bestemt emne ved hjælp af enhver tilgængelig nøgle er i det væsentlige en lineær søgning . Og så har den en kompleksitet af O (n) .

Konklusion

Kompleksitet er mere end blot et emne til diskussion af etablerede algoritmer og datastrukturer. Hvis det bruges klogt, kan det være et nyttigt værktøj til at måle effektiviteten af ​​det arbejde, du udfører, og den kode, du opretter for at løse dine problemer.

Reference:

//www.udemy.com/js-algorithms-and-data-structures-masterclass/