Für Eingaben der Größe n, für welche Werte von n hat insertion-sort beat merge-sort?

In dem Buch Introduction to algorithms (Corman), übung 1.2-2 fragt die folgende Frage über den Vergleich von Implementierungen von insertion sort und merge-sort. Für Eingaben der Größe n, insertion sort läuft in 8n^2 Schritte, während merge-sort läuft in 64n lg n Schritte; für welche Werte von n hat insertion-sort beat merge-sort?

Obwohl ich interessiere mich für die Antwort, ich bin mehr daran interessiert, wie die Antwort zu finden, Schritt für Schritt (so, dass kann ich wiederholen Sie den Vorgang zum vergleichen zwei gegebene algorithmen, wenn überhaupt möglich).

Auf den ersten Blick, dieses problem scheint ähnlich zu etwas, wie die Suche nach der break-even-point im business-Kalkül, eine Klasse, die ich mehr als 5 Jahre her, aber ich bin nicht sicher, so dass jede Hilfe wäre sehr geschätzt.

Danke

P/S Wenn meine tags sind falsch, diese Frage ist falsch kategorisiert, oder eine andere Konvention missbraucht hier bitte beschränken Sie züchtigen auf ein minimum, da dies mein erstes mal eine Frage stellen.

  • Die Lösung für 8n^2=64nlgn ist n=44. Also für 43 oder weniger Elementen zu verwenden, insertion sort, sonst mit merge-sort
  • tun die Figuren 8n^2 und 64nlogn eigentlich halten? Oder sind Sie nur hypothetische Werte für die Problemstellung?
  • problem bereits diese Werte.
InformationsquelleAutor Nate Neuhaus | 2014-10-16
  1. 29

    Da werden Sie finden, wenn insertion-sort beats merge-sort

    8n^2<=64nlogn
n^2<=8nlogn
n<=8logn

    Auf die Lösung n-8logn = 0 erhalten Sie 

    n = 43.411

    Also für n<=43 insertion sort funktioniert besser als merge-sort.

    • Danke für die Hilfe, ich konnte nicht up-vote dich, weil ich nicht ein rep von +15. Bis Stimmen jeder? 😉
    • Können Sie akzeptieren meine Antwort durch klicken auf das grüne Häkchen unterhalb der up-votes.
    • Ich danke Ihnen, sir, von der Art und Weise, können Sie mir sagen, was die Basis von log ist? Super neues material, was ich studiere auf meine freie Zeit ganz allein.
    • Um ehrlich zu sein habe ich nicht bekommen, das Ende komplett, obwohl ich dachte, dass lag an meiner zu vergessen, fast alle der Infinitesimalrechnung (lol), so dass statt zu Fragen, weiter über die Mathematik, die ich umgebucht Teil der Frage here und mir wurde gesagt, die Antwort ist falsch, und ich zitiere "das ist nicht wahr : 43.11 > 8*log(43.11) = 30.11." Irgendwelche Ideen hier?
    • Es hängt davon ab, das problem aber im Allgemeinen die Zeit, Die Komplexität von merge-sort ist O(nlogn) und Logarithmus zur Basis 2 ist. Sie können nachlesen, merge-sort, um zu verstehen, warum die Basis 2 ist.
    • Jetzt, da Sie es erwähnen, ich erinnere mich, Lesen über, die jedoch diese Diskussion nur steckte es in einen Zusammenhang für mich. Also wenn es dir nichts ausmacht, kannst du mir sagen wie man aus n-8logn = 0, um die Letzte Antwort n = 43.411? Hast du die Verwendung der Lambert-W-Funktion?
    • Ich verwendet Worlframalpha. wolframalpha.com/input/?i=n-8*log%282%2Cn%29+%3D+0
    • Können Sie uns eine Schritt-für-Schritt-Anleitung zu finden, n = 43.411 aus 'n<=8lnn' Gleichung?

    InformationsquelleAutor aandis
Schreibe einen Kommentar