Соотношение рецидива T (N) = T (3/4 * N) + O (1)

Question

Я разрабатываю рецидивирующее отношение

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

Это выходит на O(log(n)), но мне сказали раньше, что решение O(n). Отказ Я не могу найти, куда я иду не так - это выглядит так же, как отношение рецидива для двоичного поиска. Какие-либо предложения?

Answer 1

Попробуйте заменить T(n) = c*n или T(n) = c * log n в уравнение и решение. Одно из двух уравнений будет разрешимым.

Вы также можете проверить свой ответ, оценивая функцию для разных значений 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]

Одним из них сходится к небольшому положительному числу, другой пойдет на ноль или бесконечность.

Answer 2

T (N) = T (3/4 * N) + O (1) ............... (1) в вышеуказанном уравнении. T (3/4 * N) неизвестен термин Если вы спрашиваете о решении этого рецидива, то я хочу сказать, что мы можем решить это уравнение. используя метод замещения. В этом мы должны выяснить значение t (3n / 4) от основного уравнения. и замените в уравнении. рекурсивно. Поскольку это повторение зависит от рекурсии. n = 3n / 4 t (3n / 4) = t (((3/4) ^ 2 * n) + c ............... (2) Обозначение o заменено на постоянную c Отказ Теперь замените T (3N / 4) в (1) T (N) = T ((3/4) ^ 2 * N) + 2C ................ (3) Теперь поставьте n = ((3/4) ^ 2 * n) в (1) t (((3/4) ^ 2 * n) = t ((3/4) ^ 3 * n) + c заставляют t (n ) = T ((3/4) ^ 3 * N) + 3C ............... (4)

После ктуда шага уравнения. будет t (n) = t (((3/4) ^ k * n) + кс .................... (5) на этом этапе будет 2 или 1 ( Размер ввода) (3/4) ^ k * n = 1 n = (4/3) ^ k, принимая в систему с обеих сторон. log (n) = k * log (4/3) k = log (n) .............. Разместить значение в формуле. (5) t (n) = t (1) + log (n) * c .............. (6) t (n) = O (log n)

Answer 3

Ответы, которые приведены, не показывают правильный способ решения такого рода рецидивов. Вы, вы легко решаете с Теорема мастеров и в вашем случае a=1 а также b=4/3. Отказ Это означает, что c = logb(a) = 0.

Потому что твой f(n) это постоянная, вы падаете во втором корпусе и где k=0. Отказ Так что решение , куда c = 0 а также k = 0. Отказ Это означает, что:

---

O(log(n)) правильный ответ