Der beskæftiger sig med algoritmkompleksitet - dummier <[SET:descriptionda]Du allerede ved, at algoritmer er komplekse.

En del af Algorithms For Dummies Cheat Sheet

Du ved allerede, at algoritmer er komplekse. Men du skal vide, hvor kompleks en algoritme er, fordi jo mere kompliceret en er, desto længere tid tager det at køre. Den følgende tabel hjælper dig med at forstå de forskellige niveauer af kompleksitet, der præsenteres i løbet af løbstid (fra hurtigste til langsomste).

Kompleksitet	Beskrivelse
Konstant kompleksitet O (1)	Giver en uendelig eksekveringstid, uanset hvor meget input du giver. Hver indgang kræver en enkelt enhed for udførelsestid.
Logaritmisk kompleksitet O (log n)	Antallet af operationer vokser ved en langsommere hastighed end inputen, hvilket gør algoritmen mindre effektiv med små indgange og mere effektiv med større. En typisk algoritme for denne klasse er binær søgning.
Lineær kompleksitet O (n)	Operationer vokser med input i et 1: 1 forhold. En typisk algoritme er iteration, når du scanner input en gang og bruger en operation til hvert element af det.
Linearitmisk kompleksitet O (n log n)	Kompleksitet er en blanding mellem logaritmisk og lineær kompleksitet. Det er typisk for nogle smarte algoritmer, der bruges til at bestille data, såsom Mergesortsort, Heapsort og Quicksort.
Kvadratisk kompleksitet O (n 2 )	Operationer vokser som et firkant af antallet af input. Når du har en iteration inde i en anden iteration (kaldet indlejrede iterationer i datalogi), har du kvadratisk kompleksitet. For eksempel har du en liste over navne, og for at finde de mest lignende, sammenligner du hvert navn med alle de andre navne. Nogle mindre effektive ordningsalgoritmer præsenterer sådan kompleksitet: boble sortering, valg sortering og insertion sortering. Dette niveau af kompleksitet betyder, at dine algoritmer kan løbe i timer eller endda dage, før de når en løsning.
Kubisk kompleksitet O (n 3 )	Operationer vokser endnu hurtigere end kvadratisk kompleksitet, fordi nu har du flere indlejrede iterationer. Når en algoritme har denne rækkefølge af kompleksitet, og du skal behandle en beskeden mængde data (100.000 elementer), kan din algoritme løbe i årevis. Når du har en række operationer, der er en effekt af input, er det almindeligt at henvise til algoritmen som kørende i polynomisk tid.
Eksponentiel kompleksitet O (2 n )	Algoritmen tager to gange antallet af tidligere operationer for hvert nyt element tilføjet. Når en algoritme har denne kompleksitet, kan selv små problemer tage for evigt. Mange algoritmer gør udtømmende søgninger har eksponentiel kompleksitet. Det klassiske eksempel på dette niveau af kompleksitet er imidlertid beregningen af ​​Fibonacci-tal.
Faktorisk kompleksitet O (n!)	Denne algoritme præsenterer et ægte mareridt af kompleksitet på grund af det store antal mulige kombinationer mellem elementerne. Bare forestil dig: Hvis din indgang er 100 objekter, og en operation på din computer tager 10 -6 sekunder (en rimelig hastighed for hver computer i dag), skal du bruge omkring 10 140 år at fuldføre opgaven med succes (en umulig tid, fordi universets alder skønnes at være 10 14 år). Et kendte factorial kompleksitetsproblem er det rejseforhandlerproblem, hvor en sælger skal finde den korteste rute for at besøge mange byer og komme tilbage til startbyen.