Som handlar om algoritmkomplexitet - dummies <[SET:descriptionsv]Som du redan vet att algoritmer är komplexa.

En del av Algorithms For Dummies Cheat Sheet

Du vet redan att algoritmer är komplexa. Men du behöver veta hur komplex en algoritm är för att ju mer komplexa är, desto längre tid tar det att springa. Följande tabell hjälper dig att förstå de olika nivåerna av komplexitet som presenteras i ordning av körtid (från snabbast till långsammaste).

Komplexitet	Beskrivning
Konstant komplexitet O (1)	Ger en ojämn exekveringstid, oavsett hur mycket input du tillhandahåller. Varje ingång kräver en enda enhet för körningstid.
Logaritmisk komplexitet O (log n)	Antalet operationer växer långsammare än ingången, vilket gör algoritmen mindre effektiv med små ingångar och effektivare med större. En typisk algoritm för denna klass är binärsökningen.
Linjär komplexitet O (n)	Verksamheten växer med ingången i ett 1: 1-förhållande. En typisk algoritm är iteration, när du skannar in en gång och tillämpar en operation på varje del av den.
Linearitmisk komplexitet O (n log n)	Komplexitet är en blandning mellan logaritmisk och linjär komplexitet. Det är typiskt för några smarta algoritmer som används för att beställa data, till exempel Mergesortsort, Heapsort och Quicksort.
Kvadratisk komplexitet O (n 2 )	Verksamheten växer som en kvadrat av antalet ingångar. När du har en iteration inom en annan iteration (kallad nestade iterationer i datavetenskap), har du kvadratisk komplexitet. Du har till exempel en lista över namn och för att hitta de mest liknande, jämför du varje namn mot alla andra namn. Några mindre effektiva beställningsalgoritmer presenterar sådan komplexitet: bubbelsort, urvalssort och insertionssort. Denna nivå av komplexitet innebär att dina algoritmer kan springa i timmar eller till och med dagar innan de når en lösning.
Kubisk komplexitet O (n 3 )	Operationerna växer ännu snabbare än kvadratisk komplexitet, för nu har du flera nestade iterationer. När en algoritm har denna ordning med komplexitet och du behöver bearbeta en blygsam mängd data (100 000 element), kan din algoritm löpa i flera år. När du har ett antal operationer som är en kraft för ingången, är det vanligt att referera till algoritmen som löpande i polynomisk tid.
Exponentiell komplexitet O (2 n )	Algoritmen tar dubbelt så många tidigare operationer för varje nytt element som läggs till. När en algoritm har denna komplexitet kan även små problem ta evigt. Många algoritmer som gör uttömmande sökningar har exponentiell komplexitet. Det klassiska exemplet för denna nivå av komplexitet är emellertid beräkningen av Fibonacci-nummer.
Faktisk komplexitet O (n!)	Denna algoritm presenterar en riktig mardröm av komplexitet på grund av det stora antalet möjliga kombinationer mellan elementen. Tänk dig att: Om din ingång är 100 objekt och en operation på din dator tar 10 -6 sekunder (en rimlig hastighet för varje dator nuförtiden) behöver du cirka 10 140 år för att slutföra uppgiften framgångsrikt (en omöjlig tid eftersom universumets ålder beräknas vara 10 14 år). Ett känt problem med problemkomplexiteten är det resande säljareproblemet, där en säljare måste hitta den kortaste vägen för att besöka många städer och komma tillbaka till startstaden.