时间复杂度和空间复杂度详解

     有一堆数据需要排序，A要使用快速排序，B要使用堆排序，A认为自己的代码更高效，B也认为自己的代码更高效，在这种情况下，怎么来判断谁的代码更好一点呢？这时候就有了时间复杂度和空间复杂度。

目录

一、算法效率

1.1 衡量算法好坏的关键

1.2 算法的复杂度

二、时间复杂度

2.1 时间复杂度的概念

2.2 大O的渐进表示法

2.3 常见的时间复杂度的计算案例

2.3.1 案例一

2.3.2 案例二

2.3.3 案例三

2.3.4 案例四

2.3.5 案例五

2.3.6 案例六

2.3.7 案例七

2.3.8 案例八

 三、空间复杂度

3.1 空间复杂度的概念

3.2 常见的空间复杂度计算案例

3.2.1 案例一

3.2.2 案例二

3.2.3 案例三

 3.2.4 案例四

四、常见的复杂度对比

五、复杂度的练习

5.1 消失的数字

5.2 旋转数组

一、算法效率

1.1 衡量算法好坏的关键

     我们在之前探讨过斐波那契数列计算的两种方式即递归和循环，这两种方式那种更好呢？我们认为循环的方式更好，使用递归去求斐波那契数列，会有大量的重复计算，那么显然循环的方式更好，这两个代码可以直接分析出来，但是对于其他一些不容易进行分析的算法，我们用什么来作为算法好坏的标准呢？这里就引入了算法复杂度的概念。

1.2 算法的复杂度

     算法在编写成可执行程序后，运行时需要耗费时间资源和空间资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。在下面的文章中我们会依次讲解时间复杂度和空间复杂度。

二、时间复杂度

2.1 时间复杂度的概念

     时间复杂度不是算的算法所用的时间，在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一 个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知 道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

     对于算法的时间复杂度，我们不需要计算出精确的执行次数，只需要对执行次数进行估算，得到大致的量级，在计算时间复杂度和空间复杂度的时候，我们统一使用的是大O的渐进表示法。

2.2 大O的渐进表示法

     在计算算法的复杂度的时候，我们只需要得到大概次数所属的量级，即忽落掉一些对结果影响不大的项，在这里我们主要使用大O的渐进表示法。

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

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

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

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

     通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

     对于有一些算法，算法的时间复杂度存在最好、平均和最坏情况：

     1.最坏情况：任意输入规模的最大运行次数(上界)

     2.平均情况：任意输入规模的期望运行次数

     3.最好情况：任意输入规模的最小运行次数(下界)

     在实际中中一般情况关注的是算法的最坏运行情况。

2.3 常见的时间复杂度的计算案例

2.3.1 案例一

// 计算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);
}

     在上面的概念中我们知道时间复杂度就是基本语句的执行次数，在上述算法中，有两个循环，一个for循环，执行2*N次，一个while循环，执行10次，所以执行次数为2*N+10次，计算时间复杂度我们使用大O的渐进表示法，忽略掉对整体影响不大的项，所以在此算法中的时间复杂度为：O(N)。

2.3.2 案例二

// 计算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);
}

     在上述算法中，有两个for循环，按照大O的渐进表示法，上述算法的时间复杂度是：O(M+N)，在此案例中并未对M和N的大小进行说明，如果题目指明M远大于N，那就说明N对最终结果影响不大，可以忽略，时间复杂度就是：O(M);如果题目指明N远大于M，那就说明M对最终结果影响不大，可以忽略，时间复杂度就是：O(N);如果题目指明M=N，时间复杂度就是：O(N)或者O(M)。

2.3.3 案例三

// 计算Func4的时间复杂度？
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

     上述算法中，基本语句的执行次数为100，按照大O的渐进表示法，时间复杂度为：O(1)。

     在这里如果有同学不理解常数阶的执行次数为什么一律用O(1)来表示，实际上，CPU是足够快的，循环100000000次和循环100次对他而言，时间都差不多，所以他会认为是一个量级，所以常数阶都用O(1)来表示。

2.3.4 案例四

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );

     上述的strchr库函数的功能，参数介绍如下图：

     strchr函数相当于：

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

     上述函数的时间复杂度我们需要分情况来看：

//假设有一个字符串
a d c g e h e a x \0
//如果我们要在上述字符串中找a字符，那么只需要找1次就可以找到，时间复杂度为O(1)，这个情况属于最好的情况。
//如果我们要在上述字符串中找x字符，那么只需要找N（假设一共有N个字符）次就可以找到，时间复杂度为O(N)，这个情况属于最坏的情况。

      对于时间复杂度，我们一般关注的是最坏时间复杂度，所以此算法的时间复杂度为O(N)。

2.3.5 案例五

// 计算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;}
}

     上述案例是冒泡排序，冒泡排序的主题思想是两两相邻的元素进行比较，对于冒泡排序，一趟冒泡排序可以把一个数排到正确的位置上，那么N个数就需要N-1趟冒泡排序，在这里是冒泡排序的优化版本（如果想要对冒泡排序了解的更加清晰可以看看我的《数组》那篇博文），如果在进行循环的过程中，数组已经是升序那么接下来的循环就不会再继续，对于上述时间复杂度的计算，我们主要通过思想来进行分析，分为最好情况和最坏情况，如下图：

      从上图我们就可以看出，在最好情况下，只需要进行一趟冒泡排序，即N-1次的比较，所以最好时间复杂度为O(1)，在最坏情况下，我们需要进行N-1趟冒泡排序，每趟冒泡排序需要对两两相邻的数进行比较，最坏情况下的执行次数为：N-1+N-2+N-3+......3+2+1=N*(N-1)/2，按照大O的渐进表示法，此算法的最坏时间复杂度是：O(N^2)。

     对于时间复杂度，我们一般关注的是最坏时间复杂度，所以此算法的时间复杂度为O(N^2)。

2.3.6 案例六

// 计算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;elsereturn mid;}return -1;
}

     二分查找是什么？二分查找，例如我们需要在arr= {1,2,3,4,5,6,7,8,9,10}中找到7对应的下标，此时我们先看中间的数即arr[4]，此时数组中arr[4]对应的数字是5，比7小，我们从arr[5]到arr[9]范围内寻找，再次找到arr[5]到arr[9]中间的数，即arr[7],对应的数字是8，比7大，我们从arr[5]到arr[6]的范围找，再找arr[5]到arr[6]中间的数即arr[5],arr[5]对应的数为6比7小，此时再将arr[6]对应的数字与7比较，相等，二分查找的前提是有序。

     上述算法是二分查找的算法，这个算法也分为最好情况和最坏情况，最好情况是进行一次二分查找就能够找到，此时最好时间复杂度是：O(1)。

     接下来我们通过分析二分查找的算法来计算它的最坏时间复杂度，

     二分查找的时间复杂度为O(logN)。 

2.3.7 案例七

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

     上述算法涉及递归我们用图来解释：

2.3.8 案例八

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

     此处补充斐波那契数列的知识：斐波那契数列指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、55、89……满足：从第3项起，每一项都等于前两项之和，我们可以使用递归来计算斐波那契数列。

     使用递归求斐波那契数列的调用如下：

需要注意的是，在实际调用过程中，如果我们要求Fib(5)，图示如下：

     调用的模型类似于下方：

 

 三、空间复杂度

3.1 空间复杂度的概念

     空间复杂度也是一个数字表达式，是对一个算法在运行过程中临时占用存储空间大小的量度（是这个算法额外开辟的空间），空间复杂度不是程序占用了多少bytes的空间，他计算的是变量的大小，空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

     注意：函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。

3.2 常见的空间复杂度计算案例

3.2.1 案例一

// 计算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;}
}

      上述算法的空间复杂度是：O(1)，空间复杂度算的是由于算法额外需要开辟的空间，即由于算法需要额外开辟的变量个数，在上述算法中我们额外开辟了三个变量：end、exchange、i，按照大O的渐进表示法，空间复杂度即为：O(1)。

      在这里许多人会有一个误区：把函数的参数也算作额外开辟变量的个数，这种想法显然不对，函数的参数属于数据源，即给一些数据，按照算法对这些数据进行一定的处理，最后得到想要结果，这些数据不属于算法所需要的额外开辟的空间。

3.2.2 案例二

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if (n == 0)return NULL;long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;
}

     上述算法中，额外开辟了n+3个变量，首先开辟了n+1个long long类型的数据，其次开辟了一个long long*类型的变量fibArray和int类型的变量i，按照大O的渐进表示法，空间复杂度为：O(n)。

3.2.3 案例三

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

     求斐波那契递归的空间复杂度，我们依然先看递归的调用图示：

     对于上述算法，它的空间复杂度是：O(N)，主要是由于它的调用顺序：
 

 

    对于Fib(N),调用时先调用 Fib(N-1)，然后调用Fib(N-2)，一直到调用到Fib(2)，然后返回Fib(2)的值，把Fib(2)函数调用开辟的函数帧还给存储空间，然后调用Fib(1)，也就是说Fib(2)和Fib(1)是使用的同一块空间，以此类推，在此函数递归调用的过程中，有一些调用复用同一块空间，所以实际上该算法额外开辟的空间为N个，即空间复杂度为：O(N)。

     此处主要还涉及了一些关于函数栈帧的创建与销毁的知识，这部分知识大家可以从“我的资源”中找到，或者私聊我要相关的笔记。

     此处我们还可以通过求解Fib(5)来演示：
 

 

 3.2.4 案例四

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

     上述的函数递归调用与案例三有所不同，在本案例中，函数调用层层嵌套，此函数递归调用的方式类似下图:

 

     对于上述函数的每次调用我们可以认为开辟了常数个变量，需要进行N次函数调用，所以上述算法的空间复杂度是：O(N)。

四、常见的复杂度对比

一般算法常见的复杂度如下：

            （上图来源于百度，如有侵权，告知删除） 

五、复杂度的练习

5.1 消失的数字

oj链接：https://leetcode-cn.com/problems/missing-number-lcci/

5.2 旋转数组

oj链接：https://leetcode-cn.com/problems/rotate-array/

注：上面两个题大家可以先做一下，他们将在下一篇博客中具体分析。