目录
一、题目描述
二、思路分析
三、易错提醒
四、同级和嵌套的关系
一、题目描述
下列程序段的时间复杂度是（）
int sum = 0;
for (int i = 1; i < n; i *= 2)
for (int j = 0; j < i; j++)
sum++;
A. O(logn)
B. O(n)
C. O(nlogn)
D. O(n^2)
二、思路分析
首先我们先对外层循环进行分析：
外层每循环一次，i=i*2
即：i*2*2*2*2*2*...*2=n
每乘以一次2，代码执行一次；共乘了多少次2，就代表代码执行了多少次
设共执行了x次，所以：2^x=n
即x=logn
所以外层循环的时间复杂度为：O(logn)
接下来看内层循环：
我们发现，内层j的循环次数是基于外层i的值
由于j<i，每当外层循环迭代器一次，内层的循环次数就是i-1
因为i是呈指数的形式增长的
外层第一次执行循环：i=1=2^0
外层第二次执行循环：i=1=2^1
外层第三次执行循环：i=1=2^2
外层第四次执行循环：i=1=2^3
......
所以外层循环迭代器第k次的时候，i的值大概是2^（k-1）
所以外层循环第k次时，内层循环执行2^(k-1)-1次。
内层的总执行次数就是：1+2+4+8+......+2^(k-1)-1
这里求出的内层执行次数的总和，也就是内外层执行的次数
其实就是一个等比数列
等比数列求和公式有两种，当q!=1的时候，Sn=a1（1-q^n）/1-q or Sn=（a1-an*q）/1-q
因为k=logn
所以：
Sn= 1 * （1 - 2^(k-1)） / （1 - 2） = (2^k-1) = 2^(logn-1)
忽略掉1，则2^(logn-1) =n
即时间复杂度为：O(n)
综上所B述：答案为B
三、易错提醒
- 为什么求出内层总循环次数就是求出总执行次数？
- 循环嵌套不该是内层循环次数*外层循环次数吗？
- 那外层明明也执行了，那不该把外层执行次数与内层执行次数相加吗？
这是我在写这道题碰壁的三个点。
个人见解如下：
3.1 内层总循环次数就是总执行次数的原因
在之前写代码，我们遇见过这种类型的代码：
int sum = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
sum++;
}
}我们知道，它的时间复杂度是：O(n^2)
那为什么是O(n^2)呢？
那就结合图来进行详细分析一下：
所以说，内层总循环次数就是求出了总执行次数。
3.2 是否可以内外层简单相乘的情况
那为什么图1代码求的方式是外层*内层即可，而图2却不能外层*内层？也就是n*logn?
简单分析来看：
- 因为图1的代码循环终止条件是相互不关联的，都是为n，所以可以进行简单的相乘来进行。
- 而图2的代码终止条件是具有关联性的，内层的循环次数取决于外层i的值，所以要逐步分析出当外层执行一次，内层循环次数的变化，并把内层相加。
3.3 内外层执行次数是否需要相加
那外层明明也执行了，那不该把外层执行次数与内层执行次数相加吗？
结合图进行分析：
那为什么求时间复杂度求最深层语句即可，不需要加上最外层的执行次数？
因为当n取很大值的时候，cpu运行速度很快，那些较小的数值就可以忽略不计，只需要计算属于哪个量级即可。
当n很大时，图3的n^2远远大于n ，可以忽略n，所以时间复杂度为O(n^2)
图4的n远远大于logn，可以忽略logn，所以时间复杂度为O(n)
因为时间复杂度本质是计算算法的执行次数属于哪个量级！！！
故而，我们解决了以上的三个问题！
四、同级与嵌套的关系
同级关系相加 嵌套关系相乘
我们对比以下两段代码：
代码一
//嵌套
int n = 10;
int sum = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
sum++;
}
}代码二
//同级
int n = 10;
int sum = 0;
for (int i = 0; i < n; i++)
{
sum++;
}
for (int j = 0; j < n; j++)
{
sum++;
}
cout << sum << endl;
