我要评论什么是算法复杂度？
简单来说算法复杂度是用来衡量一个算法的优劣的，一个程序在运行时，对运行时间和运行空间有要求，即时间复杂度和空间复杂度。
目录
大o的渐近表达式
时间复杂度，我们常常使用大o的渐近表示法
推导大o阶的规则：
时间复杂度示例
1.
// 计算func2的时间复杂度？
void func2(int n)
{
int count = 0; //1次
for (int k = 0; k < 2 * n ; ++ k)
{
++count; //2*n次
}
int m = 10;
while (m--)
{
++count; //10次
}
printf("%d\n", count);
}得：t(n)=1+2*n+10
由第一条和第二条规则得到时间复杂度o(n).
2.
// 计算func3的时间复杂度？
void func3(int n, int m)
{
int count = 0;
for (int k = 0; k < m; ++ k) //m次
{
++count;
}
for (int k = 0; k < n ; ++ k) //n次
{
++count;
}
printf("%d\n", count);
}得：t(n)=m+n
由第一条规则或第二条规则得到时间复杂度o(n).
（因为使用n代表其中增长速度快的哪一项，则忽略掉增长速度慢的那一项，当m和n增长速度一样时为2n，则忽略系数）
3.
// 计算func4的时间复杂度？
void func4(int n)
{
int count = 0;
for (int k = 0; k < 100; ++ k) //100次
{
++count;
}
printf("%d\n", count);
}得：t(n)=100
由第三条规则得到时间复杂度o(1).
4.
// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '\0')
return null;
p_begin++;
}
return p_begin;
}①最好情况
str的第一个字符就等于character，得：t(n)=1，则时间复杂度为o(1).
②平均情况
要查找的字符在str的中间，得：t(n)=n/2，则时间复杂度为o(n).
③最差情况
要查找字符在str的末尾，得：t(n)=n，则时间复杂度为o(n).
一般的我们取最差情况来表示算法的时间复杂度
5.
// 计算bubblesort的时间复杂度？
void bubblesort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}通过上面的分析，我们可尝试求出三种情况：
最坏情况：倒序，o(n^2)
平均情况：平均情况，o(n^2）
最好情况：有序，o(n)
6.
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}分析得t(n)=log2n,即o(logn).
7.
// 计算阶乘递归fac的时间复杂度？
long long fac(size_t n)
{
if(0 == n)
return 1;
return fac(n-1)*n;
}时间复杂度：o(n).
空间复杂度示例
空间复杂度的表示也使用大o表达式。
1.
// 计算bubblesort的时间复杂度？
void bubblesort(int* a, int n)
{
assert(a); //1次
for (size_t end = n; end > 0; --end) //一次
{
int exchange = 0; //一次
for (size_t i = 1; i < end; ++i) //一次
{
if (a[i-1] > a[i])
{
swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}空间复杂度：o(1).
// 计算阶乘递归fac的空间复杂度？
long long fac(size_t n)
{
if(n == 0)
return 1;
return fac(n-1)*n;
}
开辟了n个函数栈帧，空间复杂度为o(n)
常见复杂度对比：
![[HTML]Web前端开发技术21（HTML5、CSS3、JavaScript ）HTML5 基础与CSS3 应用，border-radius，box-shadow，transform——喵喵画网页](https://images.3wcode.com/3wcode/20240728/s_0_202407281959312227.png)
发表评论