Хороший способ визуализировать эту проблему - это Рекурсивная Диаграмма Дерева.
Здесь изображены первые три уровня дерева.
Для первого уровня,у нас есть общая работа 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)
Так что теперь у нас есть простое суммирование всех уровней, равное this.
n является константойи может быть выведено из уравнения.Расширение суммирования затем дает это уравнение.
Мы можем упростить это суммирование , как показано здесь.
В Большой тэте суммирование может быть упрощенодо Θ(n*(1+log(logn)), поскольку суммирование представляет собой гармонический ряд.
Упрощая еще больше, мы имеем Θ(n+n*log(logn)), и в соответствии с правилами Большой Тэты мы можем упростить до окончательной Большой Тета Θ(nlog(logn)) в качестве первогоn будет расти медленнее и не имеет большого значения в нашем конечном уравнении.
Но подождите!Вы попросили Big O. К счастью, Big Theta предоставляет как верхнюю, так и нижнюю границу для проблемы.Большой О обеспечивает только верхнюю границу.Что это значит для нас?Большая Тэта на самом деле является Большой О, но не наоборот, позволяя вам сказать, что рекуррентное отношение составляет O(nlog(logn)).
Надеюсь, это поможет!