Relation récurrence T (n) = T (3/4 n *) + O (1)

Question

Je travaille sur la relation de récurrence

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

Il vient à être O(log(n)), mais on m'a dit d'avance que la solution est O(n). Je ne peux pas trouver où je vais mal - cela ressemble tout comme la relation de récurrence pour la recherche binaire. Toutes les suggestions?

Answer 1

Essayez de remplacer T(n) = c*n ou T(n) = c * log n dans l'équation et la résolution. L'une des deux équations résoluble.

Vous pouvez également vérifier votre réponse en évaluant la fonction pour différentes valeurs de n.

-- 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]

L'un d'entre eux vont converger vers un petit nombre positif, l'autre ira à zéro ou l'infini.

Answer 2

T (n) = T (3/4 n *) + O (1) ............... (1) dans l'équation ci-dessus. T (3/4 * n) est le terme inconnu si vous demandez au sujet de la solution de cette récurrence, je veux dire que nous pouvons résoudre ce eq. en utilisant le procédé de substitution. dans ce que nous devons savoir la valeur de T (3n / 4) de l'équation principale. et remplacer dans l'éq. récursive. Comme cette récurrence est dépend de récursivité. n = 3n / 4 T (3n / 4) = T ((3/4) ^ 2 * n) + c ............... (2) notation O remplacé par c constante. substituer maintenant T (3n / 4) dans (1) T (n) = T ((3/4) ^ 2 * n) + 2c ................ (3) maintenant mettre n = ((3/4) ^ 2 * n) (1) T ((3/4) ^ 2 * n) = T ((3/4) ^ 3 * n) + c Remplacer T (n) = T ((3/4) ^ 3 * n) + 3c ............... (4)

Après eq étape kième. sera T (n) = T ((3/4) ^ k * n) + kc ................ (5) à cette étape n sera 2 ou 1 (taille d'entrée ) (3/4) ^ k * n = 1 n = (4/3) ^ k en prenant log sur les deux côtés. log (n) = k * log (4/3) k = log (n) .............. la valeur de position dans l'équation. (5) T (n) = T (1) + log (n) * c .............. (6) T (n) = O (log n)

Answer 3

Les réponses données ne montrent pas la bonne façon de résoudre ce genre de récurrences. Vous cas est facilement résolu avec un théorème maîtres et dans votre cas a=1 et b=4/3. Cela signifie que c = logb(a) = 0.

Parce que votre f(n) est une constante, vous tombez dans le deuxième seau de cas et où k=0. Donc, la solution est , où c = 0 et k = 0. Cela signifie que:

---

O(log(n)) est une réponse correcte