【夜深人静学数据结构与算法 | 第七篇】时间复杂度与空间复杂度-Toy模板网

这篇具有很好参考价值的文章主要介绍了【夜深人静学数据结构与算法 | 第七篇】时间复杂度与空间复杂度。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言：

今天我们将来介绍时间复杂度和空间复杂度，我们代码的优劣就是依靠这个在评判，以此为背景，我们诞生出了不少的经典思路：用时间换空间，用空间换取时间。而大多数同学对此并不在意，只是草草的看一眼知道这两个词就关闭文章，但这样是不对的，只有熟练的掌握时间复杂度与空间复杂度的计算，我们才可以更好的优化自己的代码，向拥有更低的时间和空间复杂度的代码靠近。

引入：

在最开始我们并没有时间复杂度和空间复杂度这个概念，大家对一个程序的的时间与空间消耗还采用一种朴素的方法：直接运行。是骡子是马拉出来溜溜，手动计算运行时间，查看占用空间量，这种方法虽然可以应用，但是误差太大，并且费人，如果我们要观测一个运行了100000000000000次代码的程序呢？是否要一直盯着电脑直到运行结束，因此为了方便快速的对一个程序有大致的判断，我们就创造了时间复杂度和空间复杂度。

时间复杂度：

时间复杂度是衡量算法运行时间性能的指标，它表示算法运行时间随着输入规模增大而增长的趋势。时间复杂度分为最优、最坏和平均复杂度。通常，最坏时间复杂度是最重要的，因为我们需要保证算法在最坏情况下也能够很好地工作。

时间复杂度的计算方法就是将所有代码语句的时间复杂度相加，忽略掉常数项和低阶项，得到的结果就是算法的时间复杂度，用大O符号表示。例如，在一个for循环中执行n次操作，每次操作的时间复杂度是O(1)，那么整个循环的时间复杂度就是O(n)。

一些常见的时间复杂度如下所示，按照从小到大的顺序排列：

O(1)：常数时间复杂度，表示算法的执行时间不随输入规模变化而变化；
O(logn)：对数时间复杂度，表示算法的执行时间随输入规模增大而增加，但增长缓慢；
O(n)：线性时间复杂度，表示算法的执行时间随输入规模增大而线性增加；
O(nlogn)：线性对数时间复杂度，表示算法的执行时间随输入规模增大而略微增加；
O(n2)：平方时间复杂度，表示算法的执行时间随输入规模增大而增加得非常快；
O(n3)：立方时间复杂度，表示算法的执行时间随输入规模增大而增加得非常快；
O(2n)：指数时间复杂度，表示算法的执行时间随输入规模增大而呈指数级别增加。

案例：

我们来计算以下这段代码的时间复杂度：

int i, j, n;
for(i=0; i<n; ++i)
{
    for(j=0; j<n; ++j)
    {
        cout<<"Hello, World!"<<endl;
    }
}
for(int m=0;m<n;m++)
{
    cout<<"abc";
}

我们分为两步来确定这个语句的时间复杂度

1.确定出每一个语句的时间复杂度

数据初始化语句 int i, j, 的时间复杂度为O(1)；
外层for循环的时间复杂度为O(n)，循环n次；
内层for循环的时间复杂度为O(n)，循环n次；
输出语句 cout<<"Hello, World!"<<endl; 的时间复杂度也为O(1)。
最后的一个循环时间复杂度为0（n），循环n次

2.累加所有语句的时间复杂度

得到时间复杂度的式子为：1+n*n*1+n

此时按照我们的要求：忽略掉常数项和低阶项

就可以得到结果：n2.

这就是时间复杂度的计算方法。我们可以自行写一些程序判断他的时间复杂度算法。

二分法的时间复杂度是O(log (m+n))

我们为大家介绍一下C++STL库中常见算法的时间复杂度

序号	算法	时间复杂度（平均）	最坏时间复杂度	备注
1	std::sort	O(nlogn)	O(nlogn)	快速排序
2	std::stable_sort	O(nlogn)	O(nlogn)	归并排序
3	std::partial_sort	O(nlogk)	O(nlogn)
4	std::nth_element	O(n)	O(n^2)
5	std::make_heap	O(n)	O(nlogn)	堆排序
6	std::push_heap	O(logn)	O(logn)	堆排序
7	std::pop_heap	O(logn)	O(logn)	堆排序
8	std::unique	O(n)	O(n)	只保留相邻的元素
9	std::reverse	O(n)	O(n)
10	std::rotate	O(n)	O(n)
11	std::merge	O(n)	O(n)	归并排序
12	std::inplace_merge	O(nlogn)	O(nlogn)	归并排序
13	std::shuffle	O(n)	O(n)
14	std::random_shuffle	O(n)	O(n)
15	std::max_element	O(n)	O(n)
16	std::min_element	O(n)	O(n)
17	std::binary_search	O(logn)	O(logn)
18	std::lower_bound	O(logn)	O(logn)	二分查找
19	std::upper_bound	O(logn)	O(logn)	二分查找
20	std::equal_range	O(logn)	O(logn)	二分查找

篇幅原因，这里不对所有的函数都进行介绍，STL库为我们提供了大量的实用的算法函数，希望大家可以多多翻看查阅，掌握更多的STL库函数。

空间复杂度：

空间复杂度也是衡量算法性能的指标之一，它表示算法在执行过程中所需的额外空间（除了输入数据本身的内存空间）随数据规模增长而增长的趋势。通常，我们希望算法所需的额外空间尽可能小。

空间复杂度通常用字节（byte）或位（bit）来表示。算法所需的空间包括以下几种：

程序代码占用的空间，也就是代码段；
静态分配的数据空间，如全局变量、static变量等；
动态分配的数据空间，如堆空间、栈空间、指针等。

计算空间复杂度的方法和计算时间复杂度类似，也是将所有占用内存空间的代码语句和数据结构的空间占用相加。常用的空间复杂度表示方法有：

O(1)：常数空间复杂度；
O(n)：线性空间复杂度；
O(n^2)：平方空间复杂度；
O(logn)：对数空间复杂度；
O(nlogn)：线性对数空间复杂度；
O(2^n)：指数空间复杂度。

需要注意的是，计算空间复杂度时通常不考虑程序所使用的语言和编译器，而是关注算法本身使用的空间。

案例：

假设有以下代码实现，需要计算其空间复杂度：

int i, n = 100;
int* a = new int[n];
for(i=0; i<n; ++i)
{
    a[i] = i;
    cout<<a[i]<<endl;
}
delete[] a;

我们可以将计算空间复杂度的步骤拆分为以下几步：

1. 对每个语句分析其空间复杂度，确定所需内存大小。

数据初始化语句 int i, n = 100; 所需内存大小为O(1)，即4个字节（int类型）；
动态分配数组 int* a = new int[n]; 所需内存大小为O(n)，即4*n个字节；
数组元素赋值语句 a[i] = i; 不需要额外的内存空间；
输出语句 cout<<a[i]<<endl; 所需内存空间为O(1)，即sizeof(int)+sizeof(endl)字节；
动态释放数组 delete[] a; 不需要额外的内存空间。

2. 合并空间复杂度，得到总的空间复杂度。

可以发现，在代码执行过程中，所需的最大空间是数组的大小，即O(n)级别的空间复杂度。

因此，以上代码的空间复杂度为O(n)，也就是说，以输入数据大小为n运行这段代码所需的额外空间随着输入规模n的增大而线性增长。

TIPS：

在现代社会中，由于计算机的内存普遍都比较大，而算力吃紧，因此各家互联网公司的策略都是牺牲空间复杂度换取时间复杂度，这样虽然会占用用户的内存，但是在时间复杂度上大大提高了效率。

在我们编写代码的时候，经典的时间换空间复杂度的算法是桶排序。
#include <iostream>
#include <vector>
using namespace std;

void bucketSort(vector<int>& nums, int max_val) {
    vector<int> bucket(max_val + 1, 0);
    for (int i = 0; i < nums.size(); i++) {
        bucket[nums[i]]++;
    }

    int idx = 0;
    for (int i = 0; i < bucket.size(); i++) {
        while (bucket[i] > 0) {
            nums[idx++] = i;
            bucket[i]--;
        }
    }
}

int main() {
    vector<int> nums = {5, 2, 9, 4, 1, 7, 6, 8, 3};
    int max_val = *max_element(nums.begin(), nums.end());

    bucketSort(nums, max_val);
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    return 0;
}