原文：https://blog.csdn.net/f553762019/article/details/107939161
原文：https://mp.weixin.qq.com/s/7Op49Ql4Kk9_ZwI7Y0bXDg
文章目录
算法的时间复杂度和空间复杂度
首先我们先了解什么是算法，算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。但是对于同一个问题，我们去使用不同的算法，结果或许会一样，但不同的地方就在于你所用算法所耗费的资源和时间，此篇博客就是用于去衡量不同算法的优劣。
复杂度的分析
衡量不同算法的优劣，主要还是根据算法所占的空间和时间两个维度去考虑。但是，世界上不会存在完美的代码，既不消耗最多的时间，也不占用最多的空间，鱼和熊掌不可得兼，那么我们就需要从中去寻找一个平衡点，使得写出一份较为完美的代码。
一. 时间维度
是指执行当前算法所消耗的时间，我们通常用时间复杂度来描述。
算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法
事后统计法
这种方法可行，但不是一个好的方法。该方法有两个缺陷：一是要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势。
事前分析估算的方法
因事后统计方法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。
在编写程序前，依据统计方法对算法进行估算。一个程序在计算机上运行时所消耗的时间取决于下列因素：
(1) 算法采用的策略、方法；(2).编译产生的代码质量；(3) 问题的输入规模；(4)机器执行指令的速度。
时间复杂度
(1)时间频度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
(2)时间复杂度
在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
大O符号表示法
首先我们先看一个例子
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
- 1
- 2
- 3
- 4
- 5
通过「 大O符号表示法 」，这段代码的时间复杂度为：O(n) ，为什么呢?
在 大O符号表示法中，时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。
我们继续看上面的例子，假设每行代码的执行时间都是一样的，我们用 1颗粒时间 来表示，那么这个例子的第一行耗时是1个颗粒时间，第三行的执行时间是 n个颗粒时间，第四行的执行时间也是 n个颗粒时间（第二行和第五行是符号，暂时忽略），那么总时间就是 1颗粒时间 + n颗粒时间 + n颗粒时间 ，即 (1+2n)个颗粒时间，即： T(n) = (1+2n)*颗粒时间，从这个结果可以看出，这个算法的耗时是随着n的变化而变化，因此，我们可以简化的将这个算法的时间复杂度表示为：T(n) = O(n)
为什么可以这么去简化呢，因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。
所以上面的例子中，如果n无限大的时候，T(n) = time(1+2n)中的常量1就没有意义了，倍数2也意义不大。因此直接简化为T(n) = O(n) 就可以了。
常见的时间复杂度量级
常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n2)
立方阶O(n3)
K次方阶O(nk)
指数阶(2n)
上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。
下面选取一些常见的进行讲解
常数阶O(1)
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
- 1
- 2
- 3
- 4
- 5
上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。
线性阶O(n)
这个在最开始的代码示例中就讲解过了，如：
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
- 1
- 2
- 3
- 4
- 5
这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。
对数阶O(logN)
int i = 1;
while(i<n)
{
i = i * 2;
}
- 1
- 2
- 3
- 4
- 5
从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n
也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)
线性对数阶O(nlogN)
线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。
就拿上面的代码加一点修改来举例：
for(m=1; m<n; m++)
{
i = 1;
while(i<n)
{
i = i * 2;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
平方阶O(n2)
平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。
举例：
for(x=1; i<=n; x++)
{
for(i=1; i<=n; i++)
{
j = i;
j++;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)
如果将其中一层循环的n改成m，即：
for(x=1; i<=m; x++)
{
for(i=1; i<=n; i++)
{
j = i;
j++;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
那它的时间复杂度就变成了 O(m*n)
立方阶O(n³)、K次方阶O(n^k)
参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。
除此之外，其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法，有点复杂，这里就不展开了。
二、空间维度
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。
空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：
空间复杂度O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
举例：
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
- 1
- 2
- 3
- 4
- 5
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)
空间复杂度O(n)
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
- 1
- 2
- 3
- 4
- 5
- 6
这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)
1，前置知识
我们在计算时间复杂度之前的前置知识是等差数列的通项公式和求和公式以及等比数列的通项公式和求和公式
等差数列：
通项公式：an=a1+(n-1)d（d是公差）
求和公式：Sn=n(a1+an)/2
等差数列的求和公式有两种表达方式，分别是“Sn=n*a1+n(n-1)d/2”和“Sn=n(a1+an)/2”。
等差数列的首项为a1，末项为an，项数为n，公差为d。等差数列是一种常见的数列，其特点是任何相邻两项的差值相等，这个差值被称为公差。在等差数列中，首项与末项的和、次项与倒数第二项的和都相等，这性质被称为等差数列的对称性。
等比数列：
通项公式：an=a1*qn-1（q是公比）
求和公式：Sn=a1*
2，省略常数项
计算时间复杂度首先要抛开常数项的程序段
比如
图片
这一段程序中，int i=0;这一句就是常数项的程序，他只会执行一次，所以我们只计算 while循环里面执行的次数
时间复杂度是衡量一个算法运行时间长短的指标，它反映了程序执行的步骤与输入数据之间的关系。在计算时间复杂度时，我们通常关注算法运行时间随输入数据规模增长的变化趋势，而不是具体的执行时间。这是因为具体的执行时间受到很多因素的影响，如硬件性能、操作系统、编程语言等，而时间复杂度则是一个更加抽象的概念，它是算法本身效率的体现。
时间复杂度通常用大O表示法来描述。这种表示法会忽略掉常数因子和低阶项，只关注最高阶项，因为在输入规模很大时，最高阶项对算法运行时间的影响最为显著。
⭐时间复杂度分类
算法的时间复杂度是指运行算法所需的时间与问题规模之间的增长关系。通常用大O符号来表示算法的时间复杂度，也被称为渐进时间复杂度。算法时间复杂度分为以下几类：
常数时间复杂度 O(1)：无论问题规模如何变化，算法的运行时间都保持不变。
线性时间复杂度 O(n)：当输入规模n线性增加时，算法的执行时间与输入数据的大小成正比，例如简单查找。
对数时间复杂度 O(log n)：当输入规模n呈指数增长时，算法的运行时间呈对数增长趋势。
O(n log n)：线性对数复杂度，常见于快速排序和归并排序。
平方时间复杂度 O(n^2)：当输入规模n线性增加时，算法的运行时间呈现出平方增长趋势。通常见于简单的双层循环算法，如冒泡排序
立方时间复杂度O(n^3):当输入规模n线性增加时，算法的运行时间呈现出立方增长趋势。立方复杂度，通常见于三层嵌套循环算法。
指数时间复杂度 O(2^n)：当问题规模成指数增长时，算法的运行时间将会急剧增加。指数复杂度，算法的执行时间随数据规模的增加而呈指数增长，例如递归计算斐波那契数列
O(n!)：阶乘复杂度，随着n的增加，执行时间的增加速度非常快，通常见于解决旅行商问题的算法
在设计和优化算法时，理解算法的时间复杂度非常重要。因为时间复杂度直接影响着算法的效率和可扩展性，我们应该尽可能选择时间复杂度低的算法来解决问题。
方法
找程序段里面频度最大的语句
平方阶
图片
这个程序段里面频度最大的语句是第6句，是n^2
立方阶
图片
这个程序段里面频度最大的语句是第5句，是n^3
对数阶
图片
例子
✨常数时间复杂度 O(1)
常数时间复杂度 O(1) 的算法指的是无论输入规模如何变化，该算法的运行时间都保持不变。这种算法的执行时间与具体输入的数据规模无关，通常是表格查找、数组索引或者直接返回常量值等简单的操作。
组读取、索引和赋值
int array[] = {1, 2, 3, 4, 5}; // 声明一个数组
int x = array[2]; // 读取数组中第三个元素，即3
array[3] = 10; // 修改数组中第四个元素，将其改为10
判断一个整数是否为偶数或奇数
int num = 7;
if (num % 2 == 0) {
cout << num << ” is even.” << endl;
} else {
cout << num << ” is odd.” << endl;
}
返回固定长度的数组，字符串或其他数据结构
int* getFixedArray() {
return new int[5]{1, 2, 3, 4, 5}; // 返回一个固定长度的数组
}
string getFixedString() {
return “Hello, world!”; // 返回一个固定长度的字符串
}
✨线性时间复杂度O(n)
要从头到尾遍历一遍
线性时间复杂度 O(n) 的算法指的是随着输入规模n的增长，该算法的运行时间呈现出线性增长趋势。也就是说，当输入规模n增加1倍时，算法的运行时间也增加了1倍。通常情况下，O(n)的算法需要对数据进行从头到尾的遍历处理。
遍历数组或列表中的元素
int array[] = {1, 3, 5, 7, 9};
for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
cout << array[i] << ” “; // 输出数组中的每一个元素
}
以上代码中，遍历数组中的元素需要从头到尾逐个访问，时间复杂度为 O(n)。
线性搜索算法
从数组或列表的开头开始逐个比较元素的值，直到找到目标元素或遍历完整个数组或列表。
bool linearSearch(int array[], int target) {
for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
if (array[i] == target) return true;
}
return false;
}
求数组或列表的元素之和或平均值
int sum(int array[]) {
int result = 0;
for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
result += array[i];
}
return result;
}
double average(int array[]) {
return sum(array) / (double)(sizeof(array) / sizeof(array[0]));
}
✨对数时间复杂度O(log n)
对数时间复杂度 O(log n) 的算法指的是随着输入规模n的增长，该算法执行时间呈现出对数增长趋势。例如，当输入规模n增加1倍时，算法的运行时间可能会增加约2倍。常见的O(log n)算法通常是使用二分查找或者树结构等数据结构实现的。
二分查找
int binarySearch(int array[], int size, int target) {
int left = 0;
int right = size – 1;
while (left <= right) {
int mid = left + (right – left) / 2;
if (array[mid] == target) return mid;
else if (array[mid] < target) left = mid + 1;
else right = mid – 1;
}
return -1;
}
以上代码中，二分查找算法每次将元素范围缩小一半，时间复杂度为 O(log n)
堆排序算法
void heapify(int array[], int size, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && array[left] > array[largest]) largest = left;
if (right < size && array[right] > array[largest]) largest = right;
if (largest != i) {
swap(array[i], array[largest]);
heapify(array, size, largest);
}
}
void heapSort(int array[], int size) {
for (int i = size / 2 – 1; i >= 0; i–) {
heapify(array, size, i);
}
for (int i = size – 1; i > 0; i–) {
swap(array[0], array[i]);
heapify(array, i, 0);
}
}
以上代码中，堆排序算法使用了二叉堆的数据结构，每次都将元素拆分为两个相等长度的子集，并递归处理其中一个子集。因此，堆排序的时间复杂度为 O(log n)。在实现时，我们使用heapify()函数维护二叉堆的性质，用两个for循环来进行堆排序。
✨平方时间复杂度O(n^2)
平方时间复杂度 O(n^2) 的算法指的是随着输入规模n的增长，该算法执行时间呈现出平方增长趋势。例如，当输入规模n增加1倍时，算法的运行时间会增加约4倍
冒泡排序
双重for循环
void bubbleSort(int array[], int size) {
for (int i = 0; i < size – 1; i++)
for (int j = 0; j < size – i – 1; j++) if (array[j] > array[j + 1]) swap(array[j], array[j + 1]);
}
以上代码中，冒泡排序算法使用每一次内层循环来比较相邻元素的大小，并根据需要交换它们的位置，时间复杂度为 O(n^2)。在实现时，我们使用两个for循环分别遍历整个数组并比较相邻的元素。
插入排序算法
void insertSort(int array[], int size) {
for (int i = 1; i < size; i++) { int key = array[i]; int j = i – 1; while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j–;
}
array[j + 1] = key;
}
}
✨立方时间复杂度
三重循环
在这个例子中，我们使用了三重循环来演示立方阶时间复杂度的算法，其中第一重循环运行了 n 次，第二重循环也运行了 n 次，第三重循环也运行了 n 次，因此总的计算次数为 n * n * n，也就是立方阶时间复杂度 O(n^3)。
#include
using namespace std;
int main() {
int n; // 输入规模
cin >> n;
for (int i = 0; i < n; i++) { // 第一重循环
for (int j = 0; j < n; j++) { // 第二重循环
for (int k = 0; k < n; k++) { // 第三重循环
cout << i * j * k << ” “; // 立方阶计算
}
}
}
return 0;
}
在实际编程中，由于立方阶算法的效率非常低下，通常应该尽可能避免使用它，或者通过一些技巧将其转化为更高效的算法，以提高程序的性能。
✨指数时间复杂度 O(2^n)
指数时间复杂度是指算法执行的时间与数据规模 n 的指数成正比，通常表示为 O(2^n)。一种计算方式是，在算法中使用了嵌套循环或递归，每次运算次数都是上一次的两倍或更多，这种情况就容易出现指数级别的时间复杂度。
斐波那契数列
#include
using namespace std;
int fib(int n) {
if (n <= 1) {
return n;
} else {
return fib(n – 1) + fib(n – 2);
}
}
int main() {
int n = 10;
for (int i = 0; i < n; i++) {
int res = fib(i);
cout << res << ” “;
}
cout << endl;
return 0;
}
二、空间复杂度概念
空间复杂度是衡量算法在执行过程中对物理存储空间的需求量。它是一个函数，表示为算法输入数据的规模n的函数。空间复杂度分析告诉我们，对于给定的输入规模，算法需要多少内存空间才能顺利执行。
需要注意的是，在编程中，单个语句本身不直接“占用”内存，但它可能会导致程序在执行时使用内存。例如，变量声明、对象创建或函数调用这类语句会在内存中分配空间以存储变量、对象或开启新的函数执行上下文。
编译后的程序代码也需要存储空间，但这通常不计入空间复杂度分析，因为空间复杂度关注的是算法执行时的存储需求，尤其是相对于输入数据规模的增长情况。在空间复杂度分析中，我们关注的是算法运行过程中动态分配的内存空间，比如变量、数据结构的存储需求，以及调用栈对于递归函数的需求。
以下是空间复杂度的几个关键点：
固定空间：这部分空间不随问题规模变化，例如变量和常量所占用的空间。
变量空间：这包括动态分配的空间和递归栈空间，它会随着问题规模的变化而变化。
总空间需求：算法总的空间需求是固定空间和变量空间的总和。
3，计算时间复杂度
计算时间复杂度就是计算执行某个程序需要执行多少次，着重计算带有阶数的程序段 比如上图代码while循环带有阶数，我们只计算while循环里面的时间复杂度，易知会 执行n次，所以时间复杂度为o(n)。
下面就介绍一下计算时间复杂度的通用方法是什么
比如这个例子
void fun(int n)
{
int i=1;
while(i<=n)
{
i*=2
}
}
2x<=n 我们省略常数项int i=0,我们只计算while循环里面执行的次数 我们知道，计算时间复杂度就是计算程序程序的次数，所以我们这里计算while循环总 共执行了多少次 执行次数 i 第一次执行 i=2 第二次执行 i=4 第三次执行 i=8 …… …… 以此类推：2,4,8,16,……，可以发现i的值构成了一个等比数列，其中公比是2，第n 项an=2*2(n-1)=>an=2n
我们知道while循环执行结束的条件是i>n，我们假设执行了k次之后i>n，也就是不 满足while循环条件了，这个k值就是我们要求的时间复杂度的规模
所以根据an我们得到一个不等式,，当执行k次之后an的值>n,也就是2k什么时候大于n，求得k值即可：
2k=n时，k=log2n
所以当k大于时，while循环结束，k值就是我们要求的时间复杂度规模，所以这个例子的时间复杂度就是O(log2n)
4，案例
（1）求下列程序段的时间复杂度
count=0
for(k=1;k<=n;k*=2) ①
for(j=1;j<=n;j++) ②
count++;
首先计算①执行的次数
可以发现k构成一个等比数列，an=2^(n-1)，当k=n时，执行了次，也就说① 的时间复杂度为O()
我们在判断②的时间复杂度，②中执行的次数和外层循环无关，依次是：1,2,3,4……n， 所以可以发现构成一个等差数列，公差是1，an=n，当执行了n次之后循环结束时间， 故复杂度为O(n)
我们计算程序执行的次数只和内层循环执行的次数有关，也就是和count++执行的次数 有关，我们计算count++执行的次数就是计算整个程序执行的次数，也就是这个程序段的时间复杂度是log2n
可以发现，count++执行的次数有内层循环和外出循环决定，也就是他俩相乘的结果 就是count++执行的次数，上面我们说了外层循环复杂度是，而内层循环每次执行n次，所以总的时间复杂度是n*，也就是O(n*log2n)
这个程序段内层循环和外层循环无关，所以外层循环执行一次，内层循环都会执行n 次，当内层循环收到外层循环的限制时，时间复杂度就需要另算了