[讨论]时间复杂度 — 编程爱好者社区

主题：[讨论]时间复杂度

jhl316 [专家分：0] 发布于 2006-09-28 21:17:00

[size=3][/size][color=0000FF][/color]
for(i=1;i<n;i++)
{ j=i;
   while(j<n)
    j*=2;
  }
求该程序的时间复杂度？
谢谢了啊！

本帖地址： http://bbs.pfan.cn/post/194921.html

回复列表（共6个回复）

沙发

rickone [专家分：15390] 发布于 2006-09-29 08:51:00

外循环是n，内循环接近logn
O(nlogn)

板凳

jhl316 [专家分：0] 发布于 2006-09-29 23:15:00

外循环是N吗？
确定吗？

3 楼

雨523 [专家分：200] 发布于 2006-09-30 14:28:00

同rickone

4 楼

senzhang [专家分：160] 发布于 2006-10-03 18:42:00

算到这样就可以了,但是如果想求精确值的话是这样nlogn-log(n!)
[quote]外循环是n，内循环接近logn
O(nlogn)[/quote]

5 楼

rickone [专家分：15390] 发布于 2006-10-04 12:53:00

我不太清楚是否 nlogn==O(log(n!))

严格的算应该是
[log(n)]+[log(n-1)]+[log(n-2)]+...+[log(1)]
有取整符号，于是按平均概率看，有一半的数值会接近[log(n-1)]，那应该是和[log(n-1)]n/2，所以觉得是O(nlogn)，至于在数学上是否有前面那个式子，我不知道。

6 楼

jhl316 [专家分：0] 发布于 2006-10-14 15:00:00

是不应该是log2(n/2)

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[讨论]时间复杂度

回复列表（共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[讨论]时间复杂度

回复列表 （共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共6个回复）