Laufzeit: Suche nach k kleinstem Element mit Selection Sort

  • Laufzeit: Suche nach k kleinstem Element mit Selection Sort

    Ich nehme an, die Antwort ist kn? Aber wenn ich versuche, den Baum zu zeichnen, sah es aus wie

    Laufzeit: Suche nach k kleinstem Element mit Selection Sort

    Also muss ich etwas mehr falsch gemacht haben detaillierte Analyse?

    22 November 2011
    Jiew Meng
1 answer
  • Zuerst hat Ihre Arbeitsliste die Länge k+2, wenn sie wahrscheinlich die Länge k haben sollte. Ich vermute, Sie wollten von n nach n-(k-1) = n-k+1 laufen.

    Wenn Sie fortlaufende Zahlen summieren möchten, ist es am einfachsten, sich die Formel zu merken (oder abzuleiten)

     1 + 2 + ... + a = a(a+1)/2
     

    Verwenden Sie diese Option, um herauszufinden, dass die Summe, nach der Sie suchen,

     n(n+1)/2 - (n-k)(n-k+1)/2 = nk + (k-k^2)/2
     

    wie Sie es richtig gefunden haben. Denken Sie jetzt an Big O. Da n>k wir nk > k^2 kennen, ist der letztere Begriff wirklich ein niedrigerer Begriff, und das Ganze ist O(nk).

    22 November 2011
    PengOneAGeek