Redigerer Stor O-notasjon (avsnitt)

== Vanlige klasser av funksjoner ==

Her er en liste over klasser av funksjoner som en ofte støter på ved analyse av algoritmer. De beskriver tidsforbruket til algoritmer når ''n'' øker mot uendelig. Funksjonene er listet med økende kompleksitet. ''c'' er en vilkårlig konstant.

{| class="wikitable"
!Notatsjon                   !! Navn  !! Eksempel
|-
|''O''(1)                                 || konstant               || Avgjør om et tall er et partall eller oddetall.
|-
|''O''(log ''n'')                         || [[logaritme|logaritmisk]] || Finn et element i en sortert liste [[binærsøk]].
|-
|''O''(''n'')                             || [[linearitet|lineær]]                || Finn et element i en usortert liste.
|-
|''O''(''n'' log ''n'')                   || loglineær                 || Sorter en liste med [[heapsort]].
|-
|''O''(''n''<sup>2</sup>)                 || kvadratisk                || Sorter en liste med [[insertion sort]].
|-
|''O''(''c''<sup>''n''</sup>)             || [[Eksponensialfunksjon|eksponensiell]]         || Finn den eksakte løsningen til [[traveling salesman]]-problemet.
|-
|''O''(''n''!)                            || [[Kombinatorikk|kombinatorisk]]  || Prøv alle mulige [[permutasjon]]er.
|}
{{Autoritetsdata}}

[[Kategori:Algoritmer‎]]
[[Kategori:Matematisk notasjon]]