Alle fag › Videregående programmering › Sortering og søk

Sortering og søk

Sammenligningsbasert sortering kan i beste fall gjøres i O(nlog⁡n)O(n\log n), som Pythons innebygde Timsort klarer. Er lista allerede sortert, gir binærsøk et raskt oppslag ved gjentatte ganger å halvere søkeområdet.

O(nlog⁡n)O(n\log n)beste mulige kompleksitet for sammenligningsbasert sortering
O(log⁡n)O(\log n)binærsøk i en sortert liste

Symboler

nnantall elementer

Eksempel

Binærsøk i en sortert liste med 4095 elementer trenger høyst ⌈log⁡2(4096)⌉=12\lceil\log_2(4096)\rceil = 12 sammenligninger.

Binærsøk krever at lista er sortert på forhånd — ellers gir den feil svar uten å varsle om det.
Øv på algoritmer og datastrukturer gratis →

← Stakk og kø · NumPy-array og vektorisering →

Del av Videregående programmering: Algoritmer og datastrukturer.