#algorithm #time-complexity #big-o #mergesort
Вопрос:
Я смотрю на лучшее время выполнения для сортировки слиянием и обнаружил следующее рекуррентное соотношение: T(n) = 2T(n/2) n/2. Я осознаю тот факт, что сортировка слиянием во всех случаях является тета(nlogn). Пытаясь решить это рекуррентное соотношение, я использую телескопирование:
T(n) = 2*T(n/2) n/2
T(n) = 2^2*T(n/4) n/4 n/2
T(n) = 2^k*T(1) (n/2 n/4 ... n/2^k)
2^k = n -> log_2(n) = k
T(n) = n n(1/2 1/4 ... 1/n)
Я не уверен, как решить суммирование в последней части… Я даже не уверен, правильно ли это. Я думаю, что в суммировании будет добавлено общее количество элементов log_2(n)? Я не уверен, как вывести, что 2T(n/2) n/2-это тета(nlogn), не используя, пожалуйста, теорему мастера…
Комментарии:
1. Вы неправильно его телескопируете. T(n) = 2T(n/2) n/2 = 2(2T(n/4) n/4) n/2 = 4T(n/4) 2n/4 n/2. После телескопирования у вас есть сумма (log n) элементов, каждый из которых равен n.
Ответ №1:
Как указано в комментарии, ваш расчет, похоже, неверен.
T(n) = 2*T(n/2) n/2
T(n) = 2*(2*T(n/4) n/4) n/2 = 4*T(n/4) 2*(n/4) n/2 = 4*T(n/4) 2*(n/2)
T(n) = 4*(2*T(n/8) n/8) 2*(n/2) = 8*T(n/8) (n/2) 2*(n/2) = 8*T(n/8) 3*(n/2)
...
T(n) = 2^k * T(n / 2^k) k*(n/2), 2^k = n ---> k = log(n)
T(n) = log(n) * T(1) log(n) * (n/2)
T(n) = logn n*log(n)/2
Поэтому временная сложность сортировки слиянием = O(n*log(n))