algorithm - 奇怪种类的递归关系

我对斐波那契级数和二进制搜索的递推关系很满意，但我不知道如何找到此算法的递推关系：

Algorithm strange-sort(A[0,,,,,,n-1])
       if n=2 and A[0]>A[1]
       {
              swap(a[0],a[1])
       }
       else if n>2
       {
              m=ceiling(2n/3)
              strange-sort(A[0.....m-1])
              strange-sort(A[n-m......n-1])
              strange-sort(A[0......m-1])
       }

如何得到此算法的递归关系它解决了什么？

最佳答案

这是Stooge Sort算法维基百科说运行时是o（nlog 3/log 1.5），通过给出正确的递归，我们可以看到原因。
注意，每个递归调用没有（1）个工作，然后进行三个大小为2n/3的递归调用这给了我们递推关系
T（n）=3T（2n/3）+O（1）
我们现在可以使用Master Theorem来解决这个问题这里，a=3，b=3/2，d=0由于logb a=log1.53>0，根据主定理，它解为o（nlog1.53）。利用对数的性质，重新排列为o（nlog 3/log 1.5），约为o（n2.70951129135…）。
希望这有帮助！

关于algorithm - 奇怪种类的递归关系，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17632464/