master-theorem - 伪代码主方法算法分析

Question

通过检查这个伪代码，你如何找到主定理中使用的 c/d 常数？

FastPower(a,b) :    
     if b = 1 
         return a 
     otherwise 
         c := a*a 
         ans := FastPower(c,[b/2]) 
     if b is odd 
         return a*ans 
     otherwise return ans 
end

Answer 1

首先，您需要找到您的递归关系： T(n) = a T(n/b) + O(D) + O(C) 其中 O(D) 是将问题划分为子问题所需的时间，O (C) 是将子问题重新组合成答案所需的时间，a 是子问题的数量，n/b 是子问题的大小。然后，一旦你有了递归，你就可以使用主定理进行分析。

在你的算法中，我相信有一个大小为 n/2 的子问题，所以 a 是 1，b 是 2。假设分析不是术语，划分的时间是 O(1)，重组的时间是 O(1)位操作。

使用主定理，O(1) = Θ(n ^{log ₂ 1} ) 所以总运行时间是 Θ(n ^{log ₂ 1} log n) = Θ(log n)