如何分析这个特定版本的快速排序？

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，我们通过快速排序来传递它，否则我们将数组的大小减少3，然后传递左边和右边的部分，所以我们将这样做，直到我们得到大小为n<4的数组为止，问题是我无法得到递归，我不确定这个算法在最坏情况分析中是否更有效

谢谢你的帮助

Answer 1

好吧，不管这个排序函数是否真的起作用，计算运行时间的方法在这里都很简单：

将运行时的数学表达式写成数组大小的函数：

T(N) = ?？

好吧，如果N <= 4，那么我们调用快速排序。现在，我们没有可用的函数定义，但不管怎样，因为它只会调用最大大小为4的输入，所以我们可以将其运行时视为常量，并将其命名为C。

如果N为4，那么我们再次调用>=，数组小3。

所以：

对于N >= 4，T(N)是2* T(N-3)。

现在，这应该为您提供了运行时分析所需的所有信息。你为什么不在这里试试，当你遇到困难的时候再来找我们呢？