Рекуррентное соотношение 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) = T (3/4 * n) + O (1) ............... (1) в выше уравнении T (3/4 * n) - неизвестный термин, если вы спрашиваете о решении этого повторения, то я хочу сказать, что мы можем решить это уравнение. используя метод подстановки. в этом мы должны узнать значение T (3n / 4) из основного уравнения. и подставить в уравнение. рекурсивно. Как это повторение зависит от рекурсии. п = 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)

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

Answer 2

Попробуйте подставить 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 3

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

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

---

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