时间复杂度问题
本帖最后由 wenmingxing 于 2016-10-13 16:16 编辑求助求助
for(int i=1;i<n;i=i*2)
for(int j=0;j<i;j++)
如何理解上述循环中，时间复杂度为O（n）？？？
设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) 对的 分析可得每次j循环执行的次数为1,2,4,8,....n/2,一共执行log2(n)次,这是等比数列2^(n-1),利用等比数列求和公式,可得总共执行和为n-1,所以为O(n) orino 发表于 2016-10-13 19:47
分析可得每次j循环执行的次数为1,2,4,8,....n/2,一共执行log2(n)次,这是等比数列2^(n-1),利用等比数列求和 ...
懂了懂了，多谢多谢
页:
[1]