Auswechslung Methode: Warum ändert sich diese Wiederholung Ungleichheit & Gleichheitszeichen und warum induktive Schritt kleinere Werte als nächster Wert verwendet

Question

I CLRS Buch las zu verstehen Rezidive mit Substitutionsmethode und fand Beispiel folgende Lösung:

Recurrence, T(n) = 2T(n/2) + n 
    Guess Solution, T(n) = O(nlgn) 
    Proof that T(n) ≤ cnlgn 

Meine Fragen sind:

Q1: warum die Lösung der Gleichung ihre Zeichen zwischen Ungleichheit & Gleichheitszeichen ändert ≤ , =?

Q2: Wir wissen, dass in der mathematischen Induktion, induktiver Schritt der nächste Wert ist, also wenn aktuelle Wert n dann sollte nächster Wert seinen (n + 1) .Aber warum sie verwendete n/2 als nächster induktiver Schritt?

Bitte helfen Sie mir diese zu erklären question.It Hilfe scharen wird mich Auswechslung Method.Thanks

Answer 1

Q1 zu verstehen: Die beiden Gleichheiten sind nur Umschreibungen der vorherigen Zeile, da log (a/b) = log (a) - log (b) und log (2) = 1

Q2: Da wir T (n) als Funktion von T (n/2) schreiben, ist ein Schritt direkt ein 2-Faktor. Wenn die Rekursionsformel T (n) = f (T (n-1)) wäre, hätten Sie den klassischen Induktionsschritt mit einer 1-Addition.

Beachten Sie auch, dass Sie in diesem Beweis davon ausgehen, dass T (1) in konstanter Zeit durchgeführt werden kann.