目录
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) 指数阶