Как решить такое повторение, чтобы выяснить сложность времени

Question

Существует такая версия сортировки слиянием, когда массив делится на n / 3 и 2n / 3 половины каждый раз (вместо n / 2 и n / 2 изначально).

Повторение здесь будет : T (n) = T (n / 3) + T (2n / 3) + n

Теперь проблема в том, как решить эту проблему, чтобы получить сложность времени этой реализации?

Answer 1

Существует Akra – Bazzi_method для вычисления сложности для некоторых более сложных случаев, для которых предназначена основная теорема.

В этом примере вы получите то же Theta(NlogN), что и для равных частей (p=1, T=Theta(n(1+Integral(n/n^2*dn)))

Answer 2

T(n) обозначает общее время, затраченное алгоритмом.

Мы можем вычислить временную сложность этого рекуррентного отношения через дерево рекурсии.

T(n)=T(n/3)+T(2n/3)+n         -------  1

Root узел T(n) равен n, Root узел будет расширен на 2 части:

T(n/3) and T(2n/3)

На следующем шаге мы найдем root значение узла T(n/3) and T(2n/3) Для вычисления T(n/3) заменить n/3 вместо n в уравнении 1

T(n/3)=T(n/9)+T(2n/9)+n/3

Для вычисления T(2n/3) заменить 2n/3 вместо n в уравнении 1

T(2n/3)=T(2n/9)+T(4n/9)+2n/3

Root узел T (n / 3) равен n / 3 root узел будет расширен на 2 части:

T (n / 9) и T (2n / 9)

Расширяйте root значение узла, пока не получите отдельные элементы, т. Е. T (1)

Расчет глубины: Для расчета глубины, n/(b^i)=1

Итак, мы получим n/(3^i) или n/((3/2)^i) Если n=9, то n/3=3, 2n/3=6 для следующего уровня n/9=1, 2n/9=2, 4n/9=4

Правая часть дерева рекурсии n->2n/3->4n/9 - это самый длинный путь, по которому мы пойдем, чтобы расширить узел root. Если мы возьмем В левой части дерева, чтобы развернуть узел root, мы будем использовать n/(3^i), чтобы найти глубину дерева, чтобы узнать, где дерево остановится

Так что здесь мы используем правую часть дерева, n/((3/2)^i)

n=(3/2)^i

log n=log(3/2)^i

i=(logn base 3/2)

Теперь вычисляем стоимость каждого уровня

Поскольку стоимость каждого уровня одинакова, т.е. n

T(n) = cost of level * depth
T(n) = n * i

T (n) = n (logn base 3/2)

Или мы можем рассчитать, используя T(n)=n+n+n..... i times т.е. T(n) = n * i

Вы даже можете найти временную сложность, используя метод Акра – Бацци