数据结构-算法的时间复杂度（1.1）

目录

1. 算法效率

2. 时间复杂度

2.1 时间复杂度的概念

2.2 大O的渐进表示法

2.3 举例说明：

写在最后：

---

1. 算法效率

我们该如何判断一个算法的好坏？

衡量一个算法的好坏，是从时间和空间两个维度比较的，

而今天，我就来详细探讨一下时间复杂度。

2. 时间复杂度

2.1 时间复杂度的概念

时间复杂度是一个函数，

而：

算法中的基本操作的执行次数，为算法的时间复杂度。

我们当然不能只用运行一段程序的速度来解释时间复杂度，

毕竟每个人电脑的CPU运行速度不同。

例：

#include <stdio.h>int main()
{int n = 10;while (n > 0){n--;}return 0;
}

这一段代码走了10次，

他的时间复杂度是O(1)。

例2：

#include <stdio.h>int main()
{int n;scanf("%d", &n);while (n > 0){n--;}return 0;
}

这段代码走了n次，

他的时间复杂度是O(N)。

那么问题来了，时间复杂度究竟是怎么求的？

2.2 大O的渐进表示法

规则：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

2.3 举例说明：

void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N ; ++ k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

这段代码前面是2*N次，后面是10次，

加起来是2*N+10，

而他的时间复杂度是O(N)

例2：

冒泡排序的时间复杂度：

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)，

而最坏的情况是要和每一个数比较交换，是O(N^2)。

所以他的时间复杂度是O(N^2)。

例3：

long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

斐波那契递归的时间复杂度是O(2^N)。

通过上述的例子，我们可以知道的是，

计算时间复杂度，计算的是该算法最坏的情况。

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。