Asymptotisk analyse og sammenligning af sorteringsalgoritmer
Det er et veletableret faktum, at flettesortering kører hurtigere end indsættelsessortering. Brug af asymptotisk analyse. vi kan bevise, at merge sort kører i O(nlogn) tid og indsættelsessortering tager O(n^2). Det er indlysende, fordi merge sort bruger en opdel-og-hersk tilgang ved rekursivt at løse problemerne, hvor sortering ved indsættelse følger en inkrementel tilgang. Hvis vi gransker tidskompleksitetsanalysen yderligere, vil vi få at vide, at indsættelsessortering ikke er så slemt nok. Overraskende nok fusionerer indsættelsessorteringsslag sortering på mindre inputstørrelse. Dette skyldes, at der er få konstanter, som vi ignorerer, mens vi udleder tidskompleksiteten. På større inputstørrelser i størrelsesordenen 10^4 påvirker dette ikke vores funktions opførsel. Men når inputstørrelser falder under, f.eks. mindre end 40, så dominerer konstanterne i ligningen inputstørrelsen 'n'. Så langt, så godt. Men jeg var ikke tilfreds med en sådan matematisk analyse. Som en datalogi undergraduat skal vi tro på at skrive kode. Jeg har skrevet et C-program for at få en fornemmelse af, hvordan algoritmerne konkurrerer mod hinanden om forskellige inputstørrelser. Og også hvorfor der udføres en så streng matematisk analyse for at etablere driftstidskompleksiteter for disse sorteringsalgoritmer.
