计算程序运行时间？
计算程序运行时间？
提问于 2012-02-19 20:06:55
我正在尝试计算出我的拆分程序的运行时间，
void splitX(int x) {
if (x<=1) {return x;};
splitX(n/2);
System.out.println("splitting in progress");
splitX(n/2);
splitX(n/2);
splitX(n/2);
}我对此相当陌生，这就是到目前为止所做的事情；
T(n) = 4T(n/2)
= 4^2T(n/2^2)
= 4^3T(n/2^3)
= 4^kT(n/2^k)
= O(log n)我是不是走对了，我有点迷惑了，你还需要考虑印刷线吗？
回答 4
Stack Overflow用户
回答已采纳
发布于 2012-02-19 21:40:04
分析到最后都是正确的，解决方案是T(n) = O(n^2)
请注意，由于4^k不是常量，所以4^kT(n/2^k) != O(log n)。
看一下分析结果：
T(n) = 4T(n/2) =
= 4^2T(n/2^2)
= 4^3T(n/2^3)
= 4^kT(n/2^k)
= 4^log(n)*T(1) =
= 4^log(n) * 1 =
= (2^log(n))^2 =
= n^2
= O(n^2)为了正式证明这一点:我们使用induction
基数：T(1) = 1 = 1^2
假设每个k <= n都有T(n) = n^2
T(2n) = 4*T(n) =(induction hypothesis) 4*n^2 = (2n)^2
因此，归纳假设是真的，并且T(n) = n^2
您也可以在wolfram alpha上查看此结果
Stack Overflow用户
发布于 2012-02-19 20:14:19
在我看来，您对您的递归函数进行log(N)调用。乘以常量- 4-不会改变复杂度，打印行也不会改变(对于所有与家庭作业相关的需求)。
Stack Overflow用户
发布于 2012-02-19 20:17:42
是的，在Big-O表示法中，它是O(log )乘以常数。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9348988
复制相关文章
相似问题
腾讯云开发者
