Relación de recurrencia T (n) = T (3/4 * n) + O (1)

Question

Me estoy resolviendo la relación de recurrencia

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

Está llegando a ser O(log(n)), pero me dijeron de antemano que la solución es O(n). No puedo encontrar dónde voy mal - esto se parece a la relación de recurrencia para la búsqueda binaria. ¿Alguna sugerencia?

Answer 1

Trate de sustituir o T(n) = c*n T(n) = c * log n en la ecuación y resolver. Una de las dos ecuaciones habrá solución.

También puede comprobar su respuesta mediante la evaluación de la función para diferentes valores 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]

Uno de éstos convergerá a un pequeño número positivo, el otro irá a cero o infinito.

Answer 2

T (n) = T (3/4 n *) + O (1) ............... (1) en eq anteriormente. T (3/4 * n) es el término desconocido si está solicitando información sobre la solución de esta recurrencia, entonces yo quiero decir que podemos resolver este eq. usando el método de sustitución. en este tenemos que averiguar el valor de T (3n / 4) de la ecuación principal. y sustituir en el eq. recursivamente. Como esta es la recurrencia depende de la recursividad. n = 3n / 4 T (3n / 4) = T ((3/4) ^ 2 * n) + c ............... (2) notación O reemplazado por la constante c. ahora sustituir T (3n / 4) en (1) T (n) = T ((3/4) ^ 2 * n) + 2c ................ (3) ahora poner n = ((3/4) ^ 2 * n) en (1) T ((3/4) ^ 2 * n) = T ((3/4) ^ 3 * n) + c Sustituir T (n) = T ((3/4) ^ 3 * n) + 3c ............... (4)

Después de la etapa k-ésimo eq. estarán T (n) = T ((3/4) ^ k * n) + kc ................ (5) en este paso n será 2 o 1 (tamaño de entrada ) (3/4) ^ k * n = 1 n = (4/3) ^ k mediante la adopción de registro en ambos lado. log (n) = k * log (4/3) k = log (n) .............. valor lugar en eq. (5) T (n) = T (1) + log (n) * c .............. (6) T (n) = O (log n)

Answer 3

Las respuestas que se dan no están mostrando la forma correcta de resolver este tipo de recurrencias. Usted caso se resuelve fácilmente con un Masters teorema y en su caso y a=1 b=4/3. Esto significa que c = logb(a) = 0.

Debido a que su f(n) es una constante, se cae en el segundo caso cubo y donde k=0. Así que la solución es , donde c = 0 y k = 0. Esto significa que:

---

O(log(n)) es una respuesta correcta