Я пытаюсь выяснить время выполнения алгоритма. Это сортировка, которая работает, разделяя проблему на наборы 2/3 (это сортировка CLR). У меня возникли проблемы с этим, вот что у меня есть:
T(n)=3T([2n]/3)+1 (1 означает, что, помимо рекурсивных вызовов, есть один обмен, который может или не может быть выполнен. Предполагая, что это сделано, это все еще только постоянная стоимость .)
T(n)=3T([2([2n]/3+1)]/3+1)+1
T(n)=3T([2([2([2n]/3+1)]/3+1)]/3+1)+1
T(n)=3T([2([2([2([2n]/3+1)]/3+1)]/3+1)]/3+1)+1
и т. д...... пока мы не сможем предположить, что в какой-то момент мы, наконец, достигли базового случая для T (n) и получили постоянное значение 1 для этого времени выполнения. Это дает нам:
3([2([2([2([2(...........)]/3+1)]/3+1)]/3+1)]/3+1)+1 with logn terms (that's the "......." in the middle). This gives:
3*(2n/3+1)^(logn)+1*logn
3*(2n/3+1)^(logn)+logn
Тогда я думаю, что, поскольку, если бы основание журнала было 2n/3+1, мы могли бы упростить его до простого 3*logn+logn, мы можем это сделать. (Я постоянно слышу, что при асимптотической записи основания бревен, которые мы выбрали, не имеют значения....)
Это становится 4logn. Коэффициент уменьшается и становится просто logn.
Это правильно? Я не уверен, правильно ли я расширил это, или были ли мои манипуляции с журналом законными... Кроме того, каков этот конечный результат - большой-O, тета и т. д. Я не уверен, на что я смотрю. ..
Спасибо.
