T (n) = T (n - sqrt (n)) + T (sqrt (n)) + 1

Question

Как решить эту рецидив? Индукция - единственный способ получить ответ?Если да, то как бы вы предположили базовый случай?

Мое предположение было O (logn) , но я не уверен, как его решить.

Answer 1

Рекуррентное соотношение:

T(1) = c
T(n) = T(n - sqrt(n)) + T(sqrt(n)) + 1

Мы можем выписать несколько терминов:

n    T(n)
-    ----
1    c
2    c + c + 1 = 2c + 1
3    2c+1 + c + 1 = 3c + 2
4    2c+1 + 2c+1 + 1 = 4c + 3
5    3c+2 + 2c+1 + 1 = 5c + 4
6    4c+3 + 2c+1 + 1 = 6c + 5
…    …
9    6c+5 + 3c+2 + 1 = 9c + 8
…    …
k    kc + k - 1 = k(c + 1) - 1

После использования некоторых терминов оно выглядит линейно.Мы можем угадать, что T (n) = k (c + 1) - 1, и попытаться доказать это.

Базовый случай: T (1) = c = 1 (c + 1) - 1 = c +1 - 1 = с.Проверено

Гипотеза об индукции: Предположим, что T (n) = n (c + 1) - 1 для всех n вплоть до k

Шаг индукции: Показать T (k + 1) = (k + 1) (c + 1) - 1. Из рекурренции имеем T (k + 1) = T (k + 1 - sqrt (k + 1)) + T (sqrt (k + 1)) + 1.Из предположения индукции это равно (k + 1 - sqrt (k + 1)) (c + 1) - 1 + sqrt (k + 1) (c + 1) - 1 + 1. Упрощенно, это (k + 1) (c + 1) -1-1 + 1 = (k + 1) (c + 1) - 1, если требуется.

Следовательно, T (n) = n (c + 1) - 1, и T (n) = O (n) в результате.