algorithm - 奇怪排序的递归关系

Question

我对斐波那契数列和二分查找的递推关系很满意，但我不知道如何找到该算法的递推关系:

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

我如何获得该算法的递推关系？它解决了什么问题？

Answer 1

这是 Stooge Sort算法。维基百科说运行时间是 O(n^{log 3/log 1.5})，通过提出正确的循环我们可以明白原因。

请注意，每个递归调用都执行 O(1) 的工作，然后进行三个大小为 2n/3 的递归调用。这给了我们递归关系

T(n) = 3T(2n / 3) + O(1)

我们现在可以使用 Master Theorem解决这个问题。此处，a = 3、b = 3/2 和 d = 0。由于 log_b a = log_1.5 3 > 0，根据主定理，这求解为 O (n^{log_1.5 3})。使用对数的性质，这重新排列为 O(n^{log 3/log 1.5})，大约为 O(n^{2.70951129135...})。

希望这对您有所帮助!