Insertion Sort
-
blurry333 schrieb:
von welcher Konstante sprichst du ?
Muss ja sehr groß sein
also meine obige konstante 1.5 muss stimmen.
ist sie beim heapsort wohl < 1´Mal rechnen. Die Konstante nenne ich k.
k*n*ln(n)=n^2 |/n
k*ld(n)=n
k=n/ln(n)Die Formel kenne ich doch irgendwoher...
Oh, wenn man k hat, muß man sich nur die k-te Primzahl suchen und weiß ungefähr, ab welchem n Quicksort schneller ist.
k=1000000 => n=16626508,9 (das hier kann der Taschenrechner komischerweise wieder)
Kann jemand zum Vergleich mal die millionste Primzahl rausfinden und danebenstellen?
-
Zwischenstand:
0,89= 1/n * 2^n
wie löst man das ??
ups das kann nicht stimmen.
-
Weit komme ich auch nicht.
1.5 * n * ld(n) = 0.25 * n^2
6 * n * ld(n) = n^2
6 * n * ln(n)/ln(2) = n^2
6 * ln(n)/ln(2) = n
6/ln(2) = n/ln(n)Riecht nach http://de.wikipedia.org/wiki/Lambertsche_W-Funktion
Aber mit der bin ich total ungeübt.
Und jetzt sagt der Taschenrechner n=29.21048705, durch das Umformen ist es für ihn wohl einfacher geworden.
1.5 * n * ld(n) = 213.31
0.25 * n^2 = 213.31
Ok, stimmt.
-
Für sowas ist wolframalpha praktisch: http://www.wolframalpha.com/input/?i=6%2Fln(2)+%3D+n%2Fln(n)+