Komplexitetsklasser

Varje klass beskriver en tillväxtgräns under en definierad kostnadsmodell. Välj en klass och jämför tids- och minnesexempel. En algoritm kan ha olika gränser för tid och minne.

Artiklar och praktiska exempel

• Konstant (O(1)): En konstant mängd arbete eller minne behövs oavsett hur stor indatan blir.

• Kubisk (O(n³)): Antalet operationer eller minnesceller växer med kuben på indatastorleken.

• Exponentiell (O(2ⁿ)): Antalet möjligheter fördubblas när ett nytt oberoende ja/nej-val läggs till.

• Fakultet (O(n!)): Antalet möjliga ordningar växer som produkten 1 × 2 × … × n.

• Linjär (O(n)): Arbetet eller extraminnet växer i direkt proportion till antalet element.

• Linjärlogaritmisk (O(n log n)): Ungefär logaritmiskt många nivåer bearbetar tillsammans n element per nivå.

• Logaritmisk (O(log n)): Varje steg tar bort en bestämd andel av de återstående möjligheterna, vilket ger ett logaritmiskt antal steg.

• Kvadratisk (O(n²)): Arbete eller antalet lagrade celler växer proportionellt mot kvadraten på indatastorleken.

• Kvadratrot (O(√n)): Antalet operationer eller minnesceller växer med kvadratroten ur ett numeriskt värde n.

Så använder du avsnittet

Börja med översikten, läs en artikel och kontrollera resultatet med små exempel. Följ länkarna till närliggande avsnitt när du behöver mer bakgrund.