中文XML论坛 - 专业的XML技术讨论区--显示贴子

以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『计算机考研交流』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  问个有关时间复杂度计算的问题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=37965)

--  作者：datoubaicai
--  发布时间：9/16/2006 12:22:00 PM

--  问个有关时间复杂度计算的问题
sum2 = 0;
for (k=1; k<=n; k*=2)
  for (j=1; j<=k; j++)
    sum2++;
该怎么分析，谢谢了．

--  作者：yangling_1985
--  发布时间：9/16/2006 3:01:00 PM

--
T(n)=1+2+4+8+...+n=(2^logn) - 1=n-1=O(n)
不知道是不是这样?

--  作者：datoubaicai
--  发布时间：9/16/2006 5:03:00 PM

--
张铭翻译的那本书P20页公式2-9
1+2+4+8+....+n=2n-1。。。。

--  作者：apolor
--  发布时间：9/16/2006 5:06:00 PM

--
如果用[logn]表示不大于logn的最大整数，则总的循环次数为2^[logn]-1次，而2^[logn]-1<=n-1，所以时间复杂度为O(n)。

--  作者：adherent
--  发布时间：9/17/2006 10:46:00 PM

--
同意楼上！

W 3 C h i n a ( since 2003 ) 旗下站点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》

42.969ms