Как решить повторение методом итераций ....?
Я пытался, но не нашел Т (п) = 3t (п / 3) + п / lg (п) Может ли кто-нибудь дать мне решение
Вероятно, это больше подходит для math.stackexchange.com.
Ответы 1
Хороший способ визуализировать эту проблему - это рекурсивная древовидная диаграмма.
Здесь нарисованы первые три уровня дерева.
Для первого уровня у нас общая работа n / lg n
Для второго уровня у нас есть 3 вызова (n/3) / lg (n/3). Суммирование этих вызовов дает общую работу n / lg (n/3) на этом уровне.
Для третьего уровня у нас есть 9 вызовов (n/9) / lg (n/9). Суммирование этих вызовов дает общую работу n / lg (n/9) или n / lg (n/3^2) на этом уровне.
Рекурсивные вызовы будут продолжаться до тех пор, пока у нас не будет вызова T (1). Это условие выполняется на n/3^k = 1 или k = log3(n).
Итак, теперь у нас есть простое суммирование всех уровней, равное это.
n - постоянная величина, которая может быть исключена из уравнения. Затем расширение суммирования дает это уравнение.
Мы можем упростить это суммирование как показано здесь.
В Big Theta суммирование может быть упрощено до Θ(n*(1+log(logn)), поскольку суммирование представляет собой гармонический ряд.
Далее, упрощая, у нас есть Θ(n+n*log(logn)), и из-за правил Большой Теты мы можем упростить до последней Большой Теты Θ(nlog(logn)), поскольку первые n будут расти медленнее и не имеют особого значения в нашем окончательном уравнении.
Но ждать! Вы просили Big O. К счастью, Big Theta дает как верхнюю, так и нижнюю границу проблемы. Big O дает только верхнюю границу. Что это значит для нас? Big Theta на самом деле является Big O, но не наоборот, позволяя вам сказать, что отношение повторяемости - это O(nlog(logn)).
Надеюсь это поможет!
Добро пожаловать в Stack Overflow, не совсем понятно, о чем вы спрашиваете. Разместите любой код, который вы уже пробовали. Также ознакомьтесь с этим постом, чтобы узнать, как быстро получить ответы. stackoverflow.com/help/how-to-ask