Привет, я пытаюсь решить следующее уравнение с основной теоремой:
Т(п) = а; для n‹= 2
Т(n) = T(√n) + а; еще
Поскольку я нашел похожее уравнение (Решение повторения T(n) = 2T(sqrt(n))) Мне интересно, правильно ли мое решение. Я получил T (n) = O (log log n). Это верно для моего уравнения выше?
Мы можем написать таблицу и искать закономерность:
n T(n)
- ----
2 a
4 T(2) + a = 2a
16 T(4) + a = 3a
256 T(16) + a = 4a
...
2^(2^k) (k+1)a
Мы заметили 2 = 2^(2^0), 4 = 2^(2^1), 16 = 2^(2^2) и так далее; начиная с двух и возводя в квадрат снова и снова, мы получаем термины, такие как 2^(2^k), для которых соответствующие значения T(n) равны просто (k+1)a.
Учитывая, что n = 2^(2^k) и T(n) = (k+1)a, мы можем решить первое из этих уравнений для k через n, а затем подставить во второе. Мы получаем это log log n = k и, следовательно, T(n) = (1 + log log n)a, которые имеют асимптотическую оценку, которую вы ищете.
Технически, чтобы завершить этот аргумент, мы должны отметить, что T(n) является монотонно неубывающей функцией, и поэтому достаточно того, что мы показали, что функция ограничена таким образом для этой конкретной последовательности значений n. В общем, функция может вести себя таким образом, что описанный выше метод анализа может быть обманут, предполагая неточную оценку. Для нормально функционирующих функций это обычно не происходит.
