Overblik

Overblik

Lidt om algoritmen:
Da sortering af data er noget man bruger meget ofte, findes der en lang række forskellige algoritmer til sortering af data.
Disse algoritmers hastighed er meget forskellig, og i det følgende afsnit vil der blive en kort gennemgang af hvordan man kan måle hastigheden af en sorteringsalgoritme.

Hastighed:
For at få et overblik over hvor hurtig en algoritme er kan man bruge "Big-Oh-notation".
Den skrives O(n), hvor n er den mængde, der måler det data, der skal behandles af algoritmen.
Antallet af steps, der tages af algoritmen er proportional med den mængde af data der skal behandles.
O(n) er ikke præcis førend n bliver et stort tal.

Alle algoritmer kan klassificeres ud fra O(n) notationen.
For at kunne gøre dette skal der findes en sammenhæng mellem det antal steps algoritmen bruger på en given mændge data.

De fleste algoritmer kan inddeles efter følgende liste, de indelt efter stigende kompleksitet:

Konstant: (O(1))Antallet af steps er uafhængigt af den mængden af data.
Best case for sekventiel søgning er O(1), hvis det element der søges efter er det første element i listen, foretages der kun en sammenligning uanset længden af listen.
O(1) betyder ikke at der altid kun kan foretages en sammmenligning, men betyder istedet at et konstant antal sammenligninger bliver brugt.
Logaritmisk: (O(log n)) - algoritmer som binær søgning.
Lineær: (O(n)) - algoritmer som det gennemsnitlige resultat af sekventiel søgning.
Log-Lineær: (O(n log n)) - algoritmer hvor den første parameter er proportionel til produktet af mængden af data n til logaritmen til data mængden (log n). Den mest effektive algoritmer er af denne type.
Kvadratet: (O(n2)) - algoritmer hvor antallet af steps afhænger af kvadratet på mængden af data.
Ved at fordoble mænden af data i disse algoritmer betyder en firdobling af arbejdet.


Et eksempel:
Sourcekode til eksempel: Algoritmer.jar
JavaSource.zip