Wiederholung von Merge-Sort - Erklärung erforderlich

Question

Dies ist die Wiederholung der Worst-Case-Laufzeit T (n) des Merge-Sort-Verfahrens.

Was ist T?

warum 2T (n/2)?

Für welche Operation ist die O (n)?

Answer 1

Der Einfachheit halber sei angenommen, daß n eine Potenz von 2, so daß jeder Schritt divide ergibt zwei Teilprobleme, die beide genau Größe n/2.

Basisfall tritt ein, wenn n = 1.

Wenn ≥ 2 n ist, Zeit für die Verschmelzungssortierschritte:

Dividieren: Gerade q als Mittelwert von p und r berechnen, der konstant statt Zeit dh Θ (1).

warum 2T (n/2)?

Conquer: lösen Recursively 2 Subprobleme, die jeweils eine Größe n/2, die 2T (n/2).

Bei dem Betrieb ist der O (n)?

Kombinieren: MERGE auf einem n-Element Subarray nimmt Θ (n) Zeit.

Zusammen ergeben sie eine Funktion, die in n linear ist, was Θ (n) ist. Daher ist die Wiederholung für die Laufzeit der Mischsortierung