查找算法执行的渐近比较量

Question

我得到了以下算法：

Supersort(A, i, j):
   if(j = i): return
   if(j = i + 1):
      if(A[i] > A[j]):
         swap(A[i], A[j])
   else:
      k = floor of ( (j-i+1)/3 )
      Supersort(A, i, j-k) // sort first two thirds
      Supersort(A, i+k, j) // sort last two thirds
      Supersort(A, i, j-k) // sort first two thirds again

而且我真的不确定如何分析该算法在最坏情况下会进行多少次比较。我不想要给我的答案，我什至不知道如何开始解决这个问题。感谢您的帮助

Answer 1

通常当你有一个递归函数时，你做的第一件事就是获得递归关系。在您的情况下，当输入的大小为 n 时，让 T(n) 成为超级排序的成本。什么是平等？前两个 if stmts 只是常量，else 花费 T(2n/3)+T(n/3)+T(2n/3) then

T(n)=2T(2n/3)+T(n/3)+C

然后你解决了那个复发。

更正：在这三种情况下，您使用 2/3。我以为其中一个是1/3。在那种情况下，递归更简单，可以使用主定理

求解

T(n)=3T(2n/3)+C

查找算法执行的渐近比较量

Finding the asymptotic amount of comparisons performed by an algorithm

algorithm

complexity-theory