算法的基本概念
算法是什么
程序=数据结构+算法
算法的五个特性
有穷性
确定性
可行性
输入
输出
算法的复杂度
时间复杂度
算法时间复杂度
事前预估算法时间开销T(n)与问题规模n的关系
这里以一层,两层,多层循环为例
一层循环
for(int i=0;i<n;i++)
{
i++;
}
这个很容易就看出来,复杂度为O(n),时间开销和n关系
如果换一个呢
int i = n * n;
while(i != 1){
i = i / 2;
}
这个便不容易看出,这里讲一下我的解题思路
1.列出循环次数t和每次循环i的值,
2.找到t和i的关系
3.确定循环停止条件
4.联立求解
在这里详细写一下
1
t | 0 | 1 | 2 | 3 |
i | n^2 | (n^2)/2 | (n^2)/4 | (n^2)/8 |
2.
i=
3.结束循环的时候,i=1,
4.
=1
求解
T=O()
同样,对于下面这个问题
while(i<n){
i*=2;
}
也不难求解
两层循环
对于两层循环,本质是求解内层循环的代码块执行次数
1.求出外层循环次数变化(i值的变化)
2列出内层循环代码块执行次数
3.求和
举个栗子
for(int i=1;i<=n;i++){
for(int j=1;j<=2*i;j++){
m++;
}
}
外层 | 1 | 2 | 3 | 4 |
内层代码块次数 | 2 | 4 | 6 | 8 |
不难看出,外层执行n次,内层每次是2*i次,进行一个求和即可
最终结果为n(n+1),即为O(n^2)
当内层循环与外层循环无关的时候,如下
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
代码块(无关代码)
}
}
外层每次循环,内层都执行m次,所以复杂度为O(m*n)
多层循环
三层循环可以看成内层循环是两层循环的两层循环,多层循环也可以这样看做。
同时,下面是一些常用的大小比较
总结
时间复杂度是算法时间开销T(n)与问题规模n的关系
标签:外层,绪论,int,复杂度,内层,算法,循环,数据结构 From: https://blog.csdn.net/gzsn_/article/details/140534061