时间复杂度问题

wenmingxing · 发表于 2016-10-13 14:59:48

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 wenmingxing 于 2016-10-13 16:16 编辑

求助求助

for(int i=1;i<n;i=i*2)
    for(int j=0;j<i;j++)

如何理解上述循环中，时间复杂度为O（n）？？？

1012662902 · 发表于 2016-10-13 16:33:07

设i最多到2^x时候跳出循环
那么x= floor（log2n）（为以2为底n的对数）
不妨设x=log2n

i为1 2 4 8 。。。2^x
那么基本操作就相当于
s=1+2+4+8+。。。+2^x=2^(x+1)-1
x=log2n代入上式
s=2n-1
时间复杂度为O(n)

就这样很好 · 发表于 2016-10-13 16:53:00

对的

orino · 发表于 2016-10-13 19:47:42

分析可得每次j循环执行的次数为1,2,4,8,....n/2,一共执行log2(n)次,这是等比数列2^(n-1),利用等比数列求和公式,可得总共执行和为n-1,所以为O(n)

wenmingxing · 发表于 2016-10-13 20:36:48

orino 发表于 2016-10-13 19:47
分析可得每次j循环执行的次数为1,2,4,8,....n/2,一共执行log2(n)次,这是等比数列2^(n-1),利用等比数列求和 ...

懂了懂了，多谢多谢

账号		自动登录	找回密码
密码			立即注册