计算程序运行时间？

我试图找出我的分裂程序的运行时间，计算程序运行时间？

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)

我在正确的轨道上，即时通讯有点困惑，您是否也要考虑印刷线？

来源

2012-02-19 Lunar

的analyzis是真的，直到最后，解决的办法是T(n) = O(n^2)

注意4^kT(n/2^k) != O(log n)因为4^k不是一个常数。
看一看的analyzis：

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
假设T(n) = n^2每个k <= n
T(2n) = 4*T(n) =(induction hypothesis) 4*n^2 = (2n)^2

因此归纳假设是真实的， T(n) = n^2

Yo ü也可以检查wolfram alpha

来源

2012-02-19 13:40:04 amit

非常感谢，你能解释一下前面的4是如何改变的吗？会改变它为3例如改变运行时间？ – Lunar 2012-02-19 16:27:04

@月球：是的。 “4在前面”导致公式成为“力量”。请注意，你的分析得到了'T（n）= 4^k * T（n/2^k）'m，这导致你达到'4 * 4 * ... * 4' [logn times]。如果它是“3在前面” - 它会是'3 * 3 * ... * 3' [logn次数]，它是'3^logn'[大于n'，小于'n^2' ] – amit 2012-02-19 16:32:05

正如我所看到的，您可以对您的递归函数进行日志（N）调用。乘以一个常数 - 4不会改变复杂性，印刷线也不会改变（对于所有与家庭作业有关的需求）。

来源

2012-02-19 12:14:18 WeaselFox

这是完全错误的，因为 “恒定” 是4^k，这不是一个常数。答案是'T（n）= O（n^2）'。您可以在我的答案或[wolfram alpha]中查看结果（http://www.wolframalpha.com/input/?i=T%28n%29+%3D+4T%28n%2F2%29%2C+T ％281％29 +％3D + 1） – amit 2012-02-19 13:44:13

@amit，当然，对不对。 – WeaselFox 2012-02-21 09:21:09

是的，在Big-O表示法中，它是O（log n）通过不变来完成。

来源

2012-02-19 12:17:41 mishadoff

这显然是错误的，因为“常数”是4^k，这不是一个常数。答案是'T（n）= O（n^2）'。您可以在我的答案或[wolfram alpha]中查看结果（http://www.wolframalpha.com/input/?i=T%28n%29+%3D+4T%28n%2F2%29%2C+T ％281％29 +％3D + 1） – amit 2012-02-19 13:44:45

是我的错，谢谢！ – mishadoff 2012-02-19 13:47:28

表达这一结果是形式的

T（N）= 4T（N/2）+ C

现在用的是= 4，B应用主theorum = 2和f（n）= c;

T（N）= O（N ^洛嘎）//基座2

T（N）= N^2

来源

2012-02-19 16:09:20 pawan

计算程序运行时间？

回答

相关问题