Rekursion T (n) = T (3/4 * n) + O (1)

Question

Ich arbeite die Rekursion aus

T(n) = T(3/4 * n) + O(1)

Es kommt heraus O(log(n)) zu sein, aber ich war vorher gesagt, dass die Lösung O(n) ist. Ich kann nicht finden, wo ich falsch werde - das sieht genauso wie die Rekursion für binäre Suche. Irgendwelche Vorschläge?

Answer 1

Versuchen T(n) = c*n oder T(n) = c * log n in die Gleichung und Lösung zu ersetzen. Einer der beiden Gleichungen auflösbar sein.

Sie können auch Ihre Antwort überprüfen, indem Sie die Funktion für verschiedene Werte von n zu bewerten.

-- Define T in your preferred language
t n | n <= 1 = 1 | otherwise = t (3/4 * n) + 1

-- If it's O(log n), then T(n)/log(n) should be asymptotically constant
-- If it's O(n), then T(n)/n should be asymptotically constant
check1 n = t n / log n
check2 n = t n / n

print [check1 1e10, check1 1e11, check1 1e12, check1 1e13]
print [check2 1e10, check2 1e11, check2 1e12, check2 1e13]

Einer von ihnen auf eine kleine positive Zahl konvergieren, der andere auf Null oder Unendlich gehen.

Answer 2

T (n) = T (3/4 * n) + O (1) ............... (1) in der obigen Gleichung. T (3/4 * n) ist unbekannt Begriff, wenn Sie über die Lösung dieser Wiederholung bitten, dann möchte ich sagen, dass wir diese eq lösen können. Verwendung von Substitutionsverfahren. in dieser müssen wir den Wert von T (3N / 4) aus dem Haupt eq erfahren. und ersetzen in der Gl. rekursiv. Da diese Wiederholung ist, hängt von Rekursion. n = 3N / 4 T (3N / 4) = T ((3/4) ^ 2 * n) + c ............... (2) durch O-Notation Konstante c ersetzt. Jetzt ersetzen T (3N / 4) in (1) T (n) = T ((3/4) ^ 2 * n) + 2c ................ (3) Jetzt stellen n = ((3/4) ^ 2 * n) in (1) T ((3/4) ^ 2 * n) = T ((3/4) ^ 3 * n) + c Ersatz T (n) = T ((3/4) ^ 3 * n) + 3c ............... (4)

Nach dem k-ten Schritt Gl. wird sein T (n) = T ((3/4) * k ^ n) + kc ................ (5) in diesem Schritt wird n 2 oder 1 (Eingangsgröße ) (3/4) * k ^ n = 1 n = (4/3) k ^ durch log auf beiden Seite nehmen. log (n) = k * log (4/3) k = log (N) .............. Stellenwert in Gl. (5) T (n) = T (1) + log (n) * c .............. (6) T (n) = O (log n)

Answer 3

Die Antworten, die gegeben sind, zeigen nicht die richtige Art und Weise, diese Art von Rezidiven zu lösen. Sie Fall ist leicht gelöst mit einem Masters Satz und in Ihrem Fall a=1 und b=4/3. Dies bedeutet, dass c = logb(a) = 0.

Da Ihr f(n) eine Konstante ist, fällt man im zweiten Fall Eimer und wo k=0. So ist die Lösung , wo c = 0 und k = 0. Dies bedeutet, dass:

---

O(log(n)) ist eine richtige Antwort