目录
大O渐进表示法
一、时间复杂度量级的判断
定义:
例一:执行2*N+1次
例二:执行M+N次
例三:执行已知次数
例四:存在最好情况和最坏情况
顺序查找
冒泡排序
二分查找
例五:阶乘递归
编辑
例六:斐波那契递归
编辑
总结:
算法时间、空间复杂度(一)-CSDN博客https://blog.csdn.net/Xiaodao12345djs/article/details/142931619?spm=1001.2014.3001.5501
大O渐进表示法
我们通常用大O渐进表示法来表示时间复杂度和空间复杂度的量级
例如:如果一个程序执行了2N+1次,那么这个程序的时间复杂度属于O(N)这个量级
一、时间复杂度量级的判断
定义:
算法中的基本操作的次数,与环境无关
例一:执行2*N+1次
时间复杂度的量级为O(N)
- 保留执行次数的最高阶
- 去掉最高阶的常系数
for(int k=0; k<2*N; k++)
{
++count;
}
while(w--)
{
++count;
}
例二:执行M+N次
时间复杂度为O(N)或者O(M)
- 如果M>>N,时间复杂度量级为O(M)
- 如果N>>M,时间复杂度量级为O(N)
- 如果相差不多,相当于执行2*N次或者2*M次,所以时间复杂度量级为O(N)或者O(M)
for(k = 0; k < M; k++)
{
count++;
}
for(k = 0; k < N ; k++)
{
count++;
}
例三:执行已知次数
时间复杂度位O(1)
for(int k = 0; k < 10; k++)
{
count++;
}
例四:存在最好情况和最坏情况
如果出现最好情况执行次数和最坏情况执行次数,看最坏情况(下限)
-
顺序查找
const char* strchr(const char* str, int characeter)
while(*str)
{
if(*str == character)
{
return str;
}
++str;
}
最好情况:执行1次就能找到
最坏情况:执行N次才能找到
时间复杂度为O(N)
-
冒泡排序
最好情况:N-1次
最坏情况:N(N-1)/2(等差数列)
时间复杂度为O(N^2)
-
二分查找
最好情况:1次
最坏情况:logN(以2为底N的对数,在C语言中会简化为logN,有的书上会简化成lgN(不推荐))
时间复杂度为O(logN)
例五:阶乘递归
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N
}
时间复杂度为O(N)
例六:斐波那契递归
long long Fib(size_t N)
{
if(N<3)
return 1;
return Fib(N-1)+Fib(N-2);
}
时间复杂度为O(2^N)
总结:
- O(1) 常数阶
- O(logN) 对数阶
- O(N) 线性
- O(N*logN) nlog阶
- O(N^2) 平方阶
- O(N^3) 立方阶
- O(2^N) 指数阶