T (n) = T (n - sqrt (n))

Question

Кто-нибудь знает, как решить эту проблему?

Основная теорема здесь не работает.

Answer 1

Кажется очевидным в O (1), так как

T(n) = T(n - sqrt(n)) = T(m) with 0 < m < n

По индукции вы получаете T (n) = T (эпсилон) с эпсилоном, близким к 0.

Вопросбольше смысла, если это было T (n) = T (n - sqrt (n)) + m

Answer 2

Вы правы, что теорема Мастера здесь не применима. Если вы посмотрите поближе, то увидите, что стоимость рекурсии равна нулю (справа нет свободных элементов: T(n) = T(m) + f(n).

Это означает, что запуск рекурсии абсолютно ничего не стоит (даже одной операции). Так что, пока ваш n уменьшается за итерации (и это происходит потому, что n > n - sqrt(n)) ваша рекурсия на самом деле бесплатна.

Таким образом, ответ O(1). Постскриптум это невозможно сделать в реальной жизни, потому что вы будете делать как минимум O (1) как стоимость рекурсии.