衡量算法的标尺-时间+空间复杂度讲解

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

对于一个问题，存在着许多解题方法，那如何评价方法的优劣呢，通常来说会考虑算法的时间复杂度和空间复杂度。下面小编就为大家介绍下算法复杂度。

一、时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。

从定义可以看出，算法中基本操作重复执行的次数与算法的时间复杂度的大小成正比，因此重点是计算算法中基本操作重复执行的次数。下面用例子来说明：

（1）常量阶O(1)

{  int temp;  temp = a；  a = b;  b = temp;}

基本的程序执行操作，语句执行次数没有达到一定规模，可以看做是常数阶的复杂度。

（2）对数阶O(logn)

int Binary_Search(int *A, int lt, int rt, int v) {    int mid;    while(lt < rt){        mid = lt + (rt - lt)/2;        if(A[mid] == v) return mid;        else if(A[mid] > v) rt = mid;        else lt = mid + 1;    }    return -1;  }

二分查找一次的时间，每执行一次都会排除一半的条件，所以是对数阶的；还有堆排序每次进行调整需要的时间复杂度，即为O(logn)。

（3）线性阶O(n)

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

for循环中的语句执行了n次，故复杂度为O(n)。

（4）平方阶

for(int i = 0; i < n; ++i)  for(int j = 0; j < n; ++j)    sum += i + j;

两层for循环，for循环中的语句执行了n²次，故复杂度为。

（5）指数阶O(2ⁿ)

动态规划中的状态压缩算法时间复杂度即为O(2ⁿ),在实际算法中这个n通常比较小，如果很大的话时间复杂度就太大了。其实质是有n种状态，每种状态都有两种属性（可以看做是0/1），如果要遍历所有状态，时间复杂度即为2ⁿ。

当然还有很多类型的复杂度，例如矩阵相乘的时间复杂度为O(n³)，快速排序的时间复杂度为O(nlogn)等。重点是掌握常用的几个算法时间复杂度，给定一个算法要会结合题目分析其时间复杂度，可以以现有算法的时间复杂度作为标准来计算某个算法的时间复杂度。

二、空间复杂度

算法所需存储空间的量度称为空间复杂度，记作：

  其中，n为问题的规模（或大小）。算法的空间复杂度考虑的是除输入和程序之外的额外空间。

空间复杂度特别要注意递归算法的空间复杂度（例如深度优先搜索），递归算法的空间复杂度相当于额外增加了一个栈空间来存储函数递归的信息。例如快速排序的空间复杂度为O(logn)，即递归的层次。

除了栈空间外，更多的是考虑额外申请的数组增加的空间复杂度，例如：归并排序中，在进行归并的时候，额外需要一个数组空间进行操作。

三、真题实战

北京工业大学2019年硕士研究生考试试题-895

下列排序算法中辅助空间代价最小的是（）

A. 快速排序    B. 归并排序   C. 堆排序   D. 基数排序

【解题思路】

从题目来看，比较的便是各排序算法的空间复杂度，快速排序最好的情况下是O(logn)，归并排序上面已经提到了是O(n)，基数排序为O(rd+n)，其中，r代表关键字的基数，d代表长度，n代表关键字的个数。堆排序为O(1)，只需要使用本身的数组进行排序，故答案为C。

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬