Вычисление рекуррентного отношения T (n) = T (n / [(log n) ^ 2]) + Θ (1) - PullRequest
Новая
       69

Вычисление рекуррентного отношения T (n) = T (n / [(log n) ^ 2]) + Θ (1)

2 голосов
/ 17 марта 2020

Я пытался решить эту проблему много часов, и я думаю, что решение O (log n / [log (log n) ^ 2]). но я не уверен. Правильно ли это решение?

1 Ответ

2 голосов
/ 17 марта 2020

Разверните уравнение: 

T(n) = (T(n/(log^2(n)*log(n/log^2(n))^2) + Theta(1)) Theta(1) = 
        T(n/(log^4(n) + 4 (loglog(n))^2 - 4log(n)loglog(n)) + 2 * Theta(1)

Мы знаем, n/(log^4(n) + 4 (log(log(n)))^2 - 4log(n)log(log(n)) больше, чем n/log^4(n), асимптотически. Как видите, каждый раз n делится на log^2(n). Следовательно, мы можем сказать, что если мы вычислим высоту деления n на log^2(n) до достижения 1, это будет нижняя граница для T(n).

Следовательно, высота дерева расширения будет k такой, что 

n = (log^2(n))^k = lof^2k(n) =>‌ (take a log) 
    log(n) = 2k log(log(n)) => k = log(n)/(2 * log(log(n)))

Следовательно, T(n) = Omega(log(n)/log(log(n))).

Для верхней границы, поскольку мы знаем, что n/(i-th statement) <‌ n/log^i(n) (вместо применения log^2(n), мы применили log(n)), мы можем сказать высоту деления n на log(n) будет верхняя граница для T(n). Следовательно, как: 

n = log^k(n) => log(n) = k log(log(n)) => k = log(n) / log(log(n))

мы можем сказать T(n) = O(log(n) / log(log(n))).

...