时间复杂度o(n)和数学计算一样吗

数据结构在嵌入式和算法开发中是不可或缺的一部分，我们常常会遇到栈、树、链表等概念。但在深入学习这些之前，我们需要理解实际复杂度和空间复杂度的重要性，这就像是二进制之于计算机一样基础。本次，我们将深入探讨时间复杂度和空间复杂度的计算方式。

时间复杂度，简而言之，就是算法中代码执行的次数。例如一个for循环，如果循环N次，那么它的执行次数就是N，时间复杂度为N。

了解时间复杂度后，我们再来聊聊大O渐进表示法。它是用来表示复杂度的，用大写字母O来表示，例如O(n)。那么大O渐进表示法是什么呢？具体如下：

1. 忽略运行时间中的所有加法常数，只保留其中的常数项。

3. 如果最高阶项存在且不为1，则去掉与其相乘的常数。这样得到的结果就是大O阶。

接下来，我们详细讲解四种常见的时间复杂度：O(1)、O(N)、O(N²)和O(log N)。

实例分析

1.

考虑一段代码，其运行次数可以表示为F(N) = N² + 2N + 10。当N趋向无穷大时，2N+10的影响变得微乎其微，可以忽略不计。我们得到F(N) ≈ N²。按照大O表示法，其时间复杂度为O(N²)。

2.

对于公式F(N) = 2N + 10，当N增大时，10这个常数项可以忽略不计，连系数2也可以忽略。其时间复杂度为O(N)。

3.

如果某段代码的执行次数是一个固定的常数，例如F(N) = 100，那么我们可以将其表示为O(1)。

4.

有一个实现冒泡排序的算法。考虑一组数据a[5] = {1,2,3,4,5}，该算法需要将最大的数逐渐冒泡到数组的最后。通过观察可以发现，该算法的时间复杂度与数据的数量N有关。具体地，它的执行次数为一个等差数列的和，当N趋向无穷大时，其时间复杂度为O(N²)。

5.

还有一个例子是二分查找法。当数据按照正确的大小顺序排列时，我们通过二分查找法来找到我们想要的数据。每次查找都会排除掉一半的数据。二分查找法每次执行大约需要两次操作，假设查找了X次找到了目标数据，那么X大约等于logN。二分查找的时间复杂度为O(log N)。