Как анализировать эту конкретную версию quicksort?

Question

У меня есть этот псевдокод, и я хочу, чтобы время анализа сложности этого алгоритма Но я не знаю об этом

Proc Sort(A,l,r) 
if(r-l+1<4) 
    then Quicksort(A,l,r) 
    else 
    Sort(A,l,r-3) 
    Sort(A,l+3,r) 

Так что я знаю, что если элемент массива меньше 4 мы ее через быструю сортировку else мы уменьшаем размер массива на три, а затем передаем левую и правую часть. Итак, мы сделаем это нелепо, мы получим именно массив размера n < 4 проблема в том, что я не могу дождаться повторения, и я не уверен если этот алгоритм работает лучше в худшем случае анализа

Благодарим за помощь

Answer 1

Ну, или нет на самом деле работает эта функция сортировки , способ выяснить время работы довольно легко здесь:

Вы записать математическое выражение для времени выполнения в зависимости от размера массива:

T (N) = ???

Ну, если N < = 4, то мы вызываем Quicksort. Теперь у нас нет определения функции, но независимо от этого, поскольку он будет когда-либо вызван с входом не более 4, мы можем обрабатывать его время работы как константу и просто называть его C.

И если N> = 4, мы снова вызываем Сорт, с массивами, которые на 3 меньше.

Итак:

Т (N) для N> = 4 равно 2 * Т (N-3).

Теперь на этом этапе вы должны предоставить всю необходимую информацию для анализа времени выполнения. Почему бы вам не попробовать отсюда и не вернуться к нам, когда застрянете?