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 排序算法。维基百科说运行时间是 O(n ^{log 3 / log 1.5} )，通过提出正确的递归我们可以看到原因。

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

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

我们现在可以使用主定理来解决这个问题。这里，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...} )。

希望这可以帮助！