Die Suche nach Rekurrenzrelationen eines Algorithmus

Question

ich mein Algorithmen Text Buch zu lesen, und ich lese über Rekurrenzrelationen und die Algorithmen große O Komplexität zu finden. Ich laufe über diese Zeile

"In the case of the merge-sort algorithm, we get the recurrence equation:

    t(n) = b                  if n < 2

         = 2t(n/2) +bn        if n >= 2

for b > 0

meine Antwort war "wie zum Teufel wussten wir, dass?!?!"

Also ich frage mich, ob es ein systematischer Ansatz ist, oder einfach nur ein logischer Weg, um diese Rekurrenzrelationen von den Algorithmen des Erhaltens

kann jemand erklären, wo die b und die beiden 2s kommen aus?

Answer 1

Der Merge-Sort-Algorithmus kann wie folgt zusammengefasst werden:

mergesort (array A) {
   mergesort (first half of A);
   mergesort (second half of A);
   merge the two halves and return;
}

Es ist eine O (N) Algorithmus zu verschmelzenden zwei Arrays der Länge N, das heißt seine Komplexität ist bN für eine Konstante b > 0 ist.

, um die Komplexität von mergesort Unter der Annahme, T (N). Da die Hälfte von N ist N / 2, sehen wir, dass:

mergesort (array A) {                    T(N)    =
   mergesort (first half of A);          T(N/2)  +
   mergesort (second half of A);         T(N/2)  +
   merge the two halves and return;       bN
}

, die die N = 2 Fall erklärt.

N <2 Fall (die Basis Fall, in dem Sie die Rekursion stoppen) ist trivial.

Answer 2

Nun, diese Aussage ist (vermutlich) der Abschluss einer Diskussion, oder zumindest eine Aussage des Algorithmus in Frage. Ohne die Details kann ich nur Vermutungen gemacht, die so gehen würde:

• das erste, was der Algorithmus tut, ist zu überprüfen, ob es 0 oder 1 Element zu verarbeiten gefragt werden wird. Wenn das wahr ist, gibt es sofort. So dann n < 2 gibt es ein fest Kosten - es nennt b
• Für n >= 2 teilt sich der Algorithmus seine Eingabe in zwei Teile, die jeweils eine Größe n/2 und ruft sich auf jedem Stück. Jeder solcher Aufruf wird eine Gebühr von t(n/2) hat, und es gibt zwei solche Beschwörungen
• Es ist dann eine zusätzliche Gebühr, die beiden Teile wieder zusammen zu fusionieren - diese Kosten zu n proportional sein - nennen es mal b n

Die einzige kleine Kuriosität ist, dass es nicht ganz klar ist, warum die beide konstanten Faktoren, die das gleiche sein entstehen sollten -. Aber ein Teil des Punktes der Big-O-Analyse besteht darin, dass konstanten Faktoren schließlich keine Rolle tun

Answer 3

T(n) = c if n < d
     = A*T(n/b) + f(n)

, wobei d> = 1 und es gibt ein Teilproblem und die Teilprobleme sind höchstens n / b Größe. f (n) die gesamte zusätzliche Zeit benötigt, um das Problem in Teilprobleme zu unterteilen und die Teilproblem Lösungen in eine Lösung für das gesamte Problem verschmelzen.

Das ist für Teile und Herrsche-Algorithmen.

Ich frage mich, warum es zwei Teilprobleme in Mergesort?