Sammanfattning av alla algoritmer hittills i kursen
Alla tidskomplexitetsangivelser nedan är ordogränser för värsta fallet.
Problem/algoritm övre gräns undre gräns (för problem) SÖKNING OCH SORTERING Sortering av n element n log n n log n Mergesortering n log n Heapsortering n log n Insättningssortering n^2 Urvalssortering n^2 Räknesortering n Hitta median bland n element n n Med dekomposition n Sökning i sorterad n-array log n log n Binärsökning log n Textsökning i text av längd n n n Knuth-Morris-Pratt n GRAFALGORITMER indata är en sammanhängande graf (V,E) Grafgenomgång |E| |V|+|E| Breddenförstsökning |E| Djupetförstsökning |E| Minimalt spännande träd Prim |E| log |V| Kruskal |E| log |V| Kortaste stig mellan hörn s och t, ickenegativa kantvikter Dijkstra |V|^2 Kortaste stig mellan alla par av hörn, inga cykler med negativ längd Med dynamisk programmering |V|^3 log |V| Maximalt flöde Bästa Ford Fulkerson |V|^3 ARITMETIK Multiplikation av två n-bitstal (bitkostnad) Karatsuba (Dekomposition) n^1,58 Schönhage-Strassen n log n loglog n Multiplikation av två n x n-matriser n^2 Strassen (dekomposition) n^2,81 Coppersmith-Winograd n^2,376 GEOMETRISKA ALGORITMER Avgör om en punkt ligger inuti en n-sidig polygon Med skärningsräkning n Konvexa höljet till n punkter n log n n log n Grahamscan n log n