习题（复杂度分析（上））
说明
【习题（复杂度分析（上））】习题都是本人收集而来，也是为了方便以后复习
持续更新中...
试分析下面各程序段的时间复杂度
1.
x = 90;
y = 100;
while(y > 0){
if(x > 100){
x = x -10;
y--;
}else{
x++;
}
}
解答：由于此程序段中并没有和数据规模n相关，数据规模为常量，所以
O(1)
2.
for(i = 0;
i < n;
i++){
for(j = 0;
j < m;
j++){
a[i][j] = 0;
}
}
解答：由程序段可以看出，第三行的数据规模是最大的，第一行时间复杂度为n，第二行时间复杂度为m，根据乘法法则得出第三行时间复杂度为
O(m*n)
3.
s = 0;
for(i = 0;
i < n;
i++){
for(j = 0;
j < n;
j++){
s += B[i][j];
}
sum = s;
}
解答：由程序段可以看出，第四行代码的数据规模最大，第二行时间复杂度是n，第三行也是n，同样适用乘法法则得出时间复杂度为
O(n^2)
4.
i = 1;
while(i <= n){
i = i*3;
}
解答：由程序段可以看出，第三行数据规模最大，且当i>n时才会跳出循环，每次循环相当于
i*3，共进行了n次循环，此为等比数列，得出O(log3^n)
5.
x = 0;
for(i = 1;
i < n;
i++){
for(j = 1;
j <= n-i;
j++){
x++;
}
}
解答：此程序段只有第四行代码的数据规模最大，要想进行第四行必须满足
1<=n-i，所以实际上共执行了n-1+n-2+...+1 = (n-1)(n-1+1)/2，所以时间复杂度为O(n^2)
6.
x = n;
//n > 1
y = 0;
while(x => (y+1)*(y+1)){
y++;
}
解答：此程序段第四行代码数据规模最大，当
n>=(y+1)(y+1)时候都会进入第四行，则时间复杂度\sqrt{n} //根号n
下一篇：数据结构与算法之美——复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度
推荐阅读
- 如何寻找情感问答App的分析切入点
- D13|D13 张贇 Banner分析
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 自媒体形势分析
- 2020-12(完成事项)
- Android事件传递源码分析
- Python数据分析(一)（Matplotlib使用）
- 泽宇读书会——如何阅读一本书笔记
- Java内存泄漏分析系列之二（jstack生成的Thread|Java内存泄漏分析系列之二：jstack生成的Thread Dump日志结构解析）
- ffmpeg源码分析01（结构体）