算法时间、空间复杂度（二）

目录

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