数据结构 | 算法的时间复杂度和空间复杂度（详解）

从本章节开始，我们将系统的学习数据结构，学习数据结构与算法的第一课，我永远都选复杂度分析，在我看来，这是数据结构与算法中最重要的知识点。

1.什么是数据结构

数据结构是计算机科学中研究组织和存储数据的一种方式。它涉及将数据以某种特定的方式组织起来，以便能够高效地访问和修改数据。数据结构通常提供了一种方式来组织数据，使其能够以一种逻辑顺序进行处理。
数据结构可以是简单的基本数据类型，比如整数、浮点数等，也可以是复杂的数据类型，比如数组、链表、栈、队列、树、图等。每种数据结构都有其自身的特点和适用的场景，不同的数据结构在解决问题时具有不同的优缺点。

2.什么是复杂度分析

• 学习数据结构时，了解复杂度分析是至关重要的。复杂度分析是评估算法效率的方法，它能够量化算法解决问题所需的计算资源，如时间和空间。

• 复杂度分析帮助我们评估算法效率、优化程序性能，避免资源浪费，并解决大规模问题。这种分析让我们能够选择最优算法，减少时间和空间占用，提高程序响应速度和资源利用率，避免不必要的资源浪费，并应对大规模数据和复杂计算问题。

• 在算法分析中，有几种常见的复杂度分析方法，包括时间复杂度和空间复杂度。今天我们主要来了解这两种复杂度。

3.时间复杂度

3.1什么是时间复杂度

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

案例1：

    int sum = 0;
    for (int dogegg = 0; dogegg < n; dogegg++) {
        sum += dogegg;
    }

1
2
3
4
5

上面的代码总共运行的时间为多少呢？

因为是估算，所以我们估算每一行代码运行的时间为Btime，其中第一行代码运行时间为1Btime，第二行和第三行则分别运行了n次，所以每个都需要运行nBtime个时间，所以加起来可得运行时间为（1+2n)*Btime个时间

由于上面的代码比较简单，我们可以准确的算出来这个代码运行所需时间的具体值，但平时对我们的每个代码进行这样的求解显然是不太可能的，所以我们这里引用大O表示法

3.2什么是大O表示法

大O表示法是用于衡量算法时间复杂度和空间复杂度的一种标准记法。它描述了算法在处理不同规模输入时的运行时间或空间占用增长率。大O表示法提供了一种便捷的方式来比较算法之间的效率，并预测算法在处理大规模问题时的表现。

但是，大O表示法通常被用于估算算法的时间复杂度和空间复杂度。它提供了一种对算法性能的估计，而不是精确的测量，在使用大O表示法时，我们通常忽略算法的常数因子、低阶项和系数，仅关注随着问题规模增加时算法的增长趋势。

int dogeggs_sum(int n) {
    int sum = 0;
    for (int dogegg = 0; dogegg < n; dogegg++) {
        for (int i = 0; i < n; i++) {
            sum += dogegg * i;
        }
    }

1
2
3
4
5
6
7
8

接下来分析一下这段代码，其中第2行代码运行1次，第3行代码运行n次，第4，5行代码则分别运行了n^2次，所以总共运行了次。但是当n为5时,f(n)=
1+5+2*25，当 n 为 10000 的时候，f(n) = 1 + 10000 + 2 * 100000000，当 n 更大呢？

这个时候其实很明显的就可以看出来 n² 起到了决定性的作用，像常数 1，一阶 n 和 系数 2 对最终的结果（即趋势）影响不大，所以我们可以把它们直接忽略掉，所以执行的总步数就可以看成是“主导”结果的那个，也就是 f(n) = n²。
所以这个代码的时间复杂度为O(n^2)。

3.3常见时间复杂度

3.4经典案例

案例2：

// 计算Func2的时间复杂度？
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们分析可得：for循环的循环次数为2*N次，while循环的次数则为10次，所以可以将这个函数的时间复杂度分为两个部分：
1.“for“循环的时间复杂度为O（N）；
2.“while”循环的时间复杂度为O（1）；//while的循环次数为一个常数，所以表示为O（1）.
因此整个函数Func2的时间复杂度为O（N），无论N的具体值为多少，他的时间复杂度都是伴随N线性增长的。

综上，该函数的时间复杂度为$O(N)$。

案例3：

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
 int count = 0;
 for (int k = 0; k < M; ++ k)
 {
 ++count;
 }
 for (int k = 0; k < N ; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们分析可得：函数“Func3”内部包含有两个for循环,其中第一个for循环的循环次数取决于M，第二个for循环次数则取决于N，因此：
第一个for循环的时间复杂度为O（M）。
第二个for循环的时间复杂度为O（N）。
所以这个函数的时间复杂度取O（(max)M，N）。
若$M>>N$ 则取 $O（M）$
若$M<<N$ 则取 $O（N）$

案例4

// 计算Func4的时间复杂度？
void Func4(int N)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10

我们分析可得：这个函数包含有一个for循环，其中for循环进行了100次，那么这个函数的时间复杂度则为$O(100)$。
真的是这样的吗？

并不是这样计算的，当我们计算一个程序的时间复杂度时不能只看循环的次数，我们要透过现象看本质，要学会看思想。

对于这个Func4函数，他包含了一个固定迭代次数为100的for循环，因此无论输入规模N是多少，迭代的次数都是固定的，它属于常数复杂度，即该函数时间复杂度与为O（1）.

综上，该函数的时间复杂度为$O(1)$。

案例5

计算strchr的时间复杂度？

 const char * strchr ( const char * str, int character );
1

while (*str) {
	if (*str == character)
		return str;
	++str;
}

1
2
3
4
5
6

这个代码是对strchr函数的模拟实现。它使用了一个while循环来遍历字符串str，并检查每个字符是否等于character，如果找到了则返回指向这个字符的指针。如果循环结束都仍未找到目标字符，则返回空指针。

假设str字符串为{‘a’,‘b’,‘c’,‘d’,‘e’}

• 当character = ‘a’时，正好是str的第一个，后面的不需要遍历，那么在本情况下时间复杂度为$O(1)$
• 当character = ‘d’或者character = 'e’时，这两种情况都得吧整个字符串遍历完，那么这种情况下的时间复杂度为$O(n)$

这就是数据的具体情况不同，代码的时间复杂度不同。

那么根据不同情况，我们有了最好情况时间复杂度、最坏情况复杂度和平均情况时间复杂度这三个概念：

• 最好情况就是在最理想的情况下，代码的时间复杂度。对应上例变量 word 正好是列表 lst 的第 1 个，这个时候对应的时间复杂度
  O(1) 就是这段代码的最好情况时间复杂度。

• 最坏情况就是在最差的情况下，代码的时间复杂度。对应上例变量 word 正好是列表 lst 的最后一个，或者 word 不存在于列表
  lst，这个时候对应的时间复杂度 O(n) 是这段代码的最坏情况时间复杂度。

• 平均情况时间复杂度，大多数情况下，代码的执行情况都是介于最好情况和最坏情况之间，所以又出现了平均情况时间复杂度。

那怎么计算平均时间复杂度呢？这个说起来有点复杂，需要用到概率论的知识。

• 从大的方面来看，查找变量 x 在列表 lst 中的位置有两种情况：在或者不在。假设变量 x 在或者不在列表 lst 中的概率都为 1/2。
• 如果 x 在列表 lst 中，那么 x 有 n 种情况，它可能出现在 0 到 n-1 中任意位置，假设出现在每个位置的概率都相同，都为 1/n。

$(1\ast \frac{1}{n}+2\ast \frac{1}{n}+3\ast \frac{1}{n}+...+n\ast \frac{1}{n})\ast \frac{1}{2}+(n\ast \frac{1}{2})=\frac{3n+1}{4}$

所以最终的平均时间复杂度就为：

$\frac{3n+1}{4}=O(n)$

综上所述，一般取最坏结果$O(n)$即可

案例6

// 计算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;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

该算法的时间复杂度取决于数组的大小和初始顺序。
在最坏情况下，即当数组是逆序排列时，它的时间复杂度是 $O(n^2)$，其中 n 是数组的长度。在最好的情况下，即当数组已经按顺序排列时，它的时间复杂度是 $O(n)$。在平均情况下，它的时间复杂度也是 $O(n^2)$。由于它包含两个嵌套的循环，内部循环会遍历整个数组，因此在最坏情况下，时间复杂度是二次方级别的。

那为什么在最坏情况下，即当数组是逆序排列时，它的时间复杂度是 $O(n^2）$

在冒泡排序法中，如果数组时逆序排序的，即数组中的每个元素都需要通过交换移动到最终的位置，即最坏结果。
那么在这种结果下呢，外部循环需要遍历整理数组长度的次数并且内部循坏也需要遍历数组长度减去当前轮数的次数，这将导致比较和交换操作的次数随着数组的长度的增加而呈二次方级别的增长。

那为什么在最好情况下，即当数组是升序排列时，它的时间复杂度是 $O(n）$

在最好的情况下，如果给定的数组已经按照升序排列，那么冒泡排序算法只需要进行一次外部循环即可完成排序。在这种情况下，内部循环不会执行任何交换操作，因为数组中的每个元素都已经在正确的位置上
因此，在最好的情况下，外部循环只需要执行一次，而内部循环也不执行任何交换操作。这导致了总的比较和交换操作次数与数组长度 n成正比，因此时间复杂度为 $O(n)$。

总而言之，在最好的情况下，冒泡排序算法的时间复杂度是线性的，因为它只需要进行一次完整的遍历来确认数组已经按顺序排列。这种情况下的时间复杂度$O(n)$。

综上，该函数的时间复杂度为$O(2^N)$。

案例7

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n-1;
 // [begin, end]：begin和end是左闭右闭区间，因此有=号
 while (begin <= end)
 {
 int mid = begin + ((end-begin)>>1);
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid-1;![在这里插入图片描述](https://img-blog.csdnimg.cn/9c2a81cd8aab45f9b5606cdc3e8be175.png)

 else
 return mid;
 }
 return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

对于给定的 BinarySearch 函数，它实现了二分查找算法来在有序数组中查找特定元素 x。二分查找算法的基本思想是在每一步中将查找范围减半，直到找到目标元素或确认目标元素不存在为止。

• 假设这个数组有n个值

• 当所找数组在数组的最左端（如上图所示）$n/2/2/2/.../2=1$

• 那这里除了几个2就表示函数进行了几次

  $2^x=n$
  即：
  $x=lo{g}_2(n)$

所以这个函数的时间复杂度为$O(x=lo{g}_2(n))$
但是由于log函数的输入比较困难，我们规定吧$lo{g}_2(n)$写成$log(n)$(仅当底数为2时)

综上，该函数的时间复杂度为$O(x=log(n))$。

案例8：

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
 if(0 == N)
 return 1;
 
 return Fac(N-1)*N;
}
1
2
3
4
5
6
7
8

对于给定的递归函数 Fac，它用于计算给定数字的阶乘。在这个递归函数中，它首先检查输入是否为 0，如果是，则返回 1，否则递归地调用自身来计算 N 的阶乘。

该函数的时间复杂度可以通过考虑递归调用的次数来确定。在这个函数中，它会递归调用 N 次，直到 N 递减到 0 为止。因此，递归调用的次数与N成正比。

因此，这个递归函数的时间复杂度可以表示为$O(N)$。由于它的递归深度与 N 成正比，因此在计算阶乘时需要进行 N次递归调用，导致时间复杂度是线性增长的。

综上，该函数的时间复杂度为$O(N)$。

案例9

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}
1
2
3
4
5
6
7
8

对于给定的递归函数 Fib，它用于计算斐波那契数列中第 N 个数字的值。在这个递归函数中，它首先检查输入是否小于 3，如果是，则返回 1，否则递归地调用自身来计算前两个数字之和。

该函数的时间复杂度可以通过考虑递归调用的次数来确定。在这个函数中，每个递归调用会产生两个新的递归调用，因此递归树会呈指数级增长。因此，它的时间复杂度可以表示为 $O(2^N)$。

因为每个递归调用会产生指数级别的子调用，导致整个递归树的节点数随着 N的增加呈指数级增长。因此，在计算斐波那契数列时，它的时间复杂度是指数级的。

综上，该函数的时间复杂度为$O(2^N)$。