计算程序运行时间？

发布于 2025-01-07 04:51:58 字数 408 浏览 1 评论 0原文

我正在尝试计算我的分割程序的运行时间，

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)

我走在正确的轨道上吗，我有点困惑，你还必须考虑打印线吗？

原文

I am trying to work out the running time of my splitting program,

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);
}

I am fairly new to this, this is what have done so far;

T(n) = 4T(n/2)
     = 4^2T(n/2^2)
     = 4^3T(n/2^3)
     = 4^kT(n/2^k)
     = O(log n)

Am i on the right track, im getting a little confused, also do you have to account for the printing line?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

蘸点软妹酱 2025-01-14 04:51:58

分析到最后都是正确的，解为 T(n) = O(n^2)

需要注意的是 4^kT(n/2^k) != O(log n ) 因为 4^k 不是常量。

看一下分析：

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)

为了正式证明它：我们使用归纳

基数：T(1) = 1 = 1^2

假设每个 k <= n 都为 T(n) = n^2

T(2n) = 4*T(n) =(归纳假设) 4*n^2 = (2n)^2

因此归纳假设为真，且 T(n ) = n^2

您还可以在 wolfram alpha

The analyzis is true until the end, the solution is T(n) = O(n^2)

Note that 4^kT(n/2^k) != O(log n) since 4^k is not a constant.

Have a look at the 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)

To formally prove it: we use induction

base: T(1) = 1 = 1^2

Assume T(n) = n^2 for each k <= n

T(2n) = 4*T(n) =(induction hypothesis) 4*n^2 = (2n)^2

Thus the induction hypothesis is true and T(n) = n^2

You can also check this result on wolfram alpha

回复收藏 0 原文