这个排序算法的复杂度是多少？

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);
}

我完全理解归并排序、冒泡排序的复杂性，但我对此感到非常困惑。该算法的复杂度是多少。谁能解释一下吗？

Answer 1

这是傀儡排序。这是一种算法，旨在表明业余爱好者在没有首先正确分析它们的情况下确实不应该实现自己的算法。其运行时间约为O(n^3)。

Answer 2

计算起来并不难。

• 每次该算法对其自身进行 3 次调用，将当前步骤的输入部分分成 3（相等）部分。 注意：第一次调用和第三次调用是相同的。
• 局部复杂度仅为 O(1)（这意味着常数），因为它只执行交换、if 和 k 的计算