时间戳

首页 > 解决方案 > 查找算法执行的比较的渐近量

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

问题描述

我得到了以下算法：

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

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

标签： algorithmcomplexity-theory

解决方案

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

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

然后你解决那个重复。

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

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

推荐阅读