Какова сложность этого алгоритма сортировки?

Question

template<class T> void sSort(T *A, int first, int last) 
{
    if(A[first]>A[last])
        swap(A[first],A[last]);

    if(first+1>=last)
    return;
    double  k = floor((last-first+1)/3);


    sSort(A,first,last-k);
    sSort(A,first+k,last);
    sSort(A,first,last-k);
}

Я прекрасно понял сложности mergeSort, bubbleSort, но я так запутался в этом.В чем сложность этого алгоритма.Кто-нибудь может объяснить?

Answer 1

Это сортировка Stooge . Это алгоритм, созданный для того, чтобы показать, что любители действительно не должны реализовывать свои собственные алгоритмы, не проанализировав их должным образом. Время его работы составляет примерно O (n ^ 3).

Answer 2

Рассчитать не сложно.

• Каждый раз, когда этот алгоритм выполняет 3 вызова, сам разбивает на 3 (равную) часть часть ввода текущего шага. Примечание : первый вызов и третий совпадают.
• Локальная сложность - это всего лишь O (1) (что означает постоянную), поскольку она будет выполнять только обмен, if и вычисление k