复杂度
常数时间操作
我们把固定时间的操作称为常数时间操作
比如说我们定义两个变量a b
int a; int b; • 1 • 2
在这两个变量进行加减乘除操作的时候它们进行的是固定时间的操作 我们就将它们称为常数时间操作
因为在计算机眼里a和b都是由32位的01组成的（在32位的机器上）
不管a和b是什么数字相加 在计算机眼里都是进行32位数字的相加 所以我们说这个操作是常数时间的
常见的常数时间操作有
- 常见的算术运算
- 常见的位运算
- 赋值 比较 自增 自减操作等
- 数组寻址
非常数时间操作
我们使用单链表进行查找的时候就是一个非常数时间操作
单链表在内存中的逻辑结构大概是这样子的
每个单独的数据通过指针连接起来
我们假设这个单链表中有一千万个数据 那么我们查找第20万个数据和第800万个数据的时间肯定是相差很大的 这就叫做非常数时间操作
时间复杂度
我们常说的时间复杂度都是使用大O的渐进表示法来表示的
我们使用选择排序的例子来讲解时间复杂度的概念 如果对于选择排序有疑问的同学可以参考我的这篇博客
简单介绍下选择排序
给我们一个N个无序数字组成的数组
我们首先遍历0~N-1位置 找出一个最小的数字和0位置的数字交换位置
之后我们再次遍历1~N-1位置 找出一个最小的数字和1位置的数字交换位置
以此类推 我们就能得到一个有序的数组
我们上面的算法就叫做选择排序
我们来分析下上面操作的时间复杂度
第一次遍历了N个元素 找出最小数字比较了N-1次 和0位置交换了一次
第二次遍历了N-1个元素 找出最小数字比较了N-2次 和0位置交换了一次
以此类推
我们实际的操作次数为 2(N + N-1 + N-2 + N-3 + … + 1) 不难发现前面是一个等差数列
我们根据等差数列公式可以写成以下格式
a N 2 + b N + c aN^2 + bN + caN2+bN+c
其中a b c都是常数 我们舍弃掉这些常数 再只保留最高阶项
我们就能得到该算法使用大O的渐进表示法的时间复杂度为N的平方
使用大O的渐进表示法的意义
最高阶项对于一个算法的影响是最大的 举个实际的例子
假设A算法的时间复杂度为N的三次方 系数为1
B算法的时间复杂度为N的平方 系数为10
当N为100时候 A算法大概要执行一百万次操作而B算法只需要执行十万次操作就可以了
这还是在N的数字很小的情况下 在我们实际的业务逻辑中 数字N可能是用万来做单位的
空间复杂度
在除了用户提供给我们的变量空间之外额外开辟的空间叫做空间复杂度 我们一般也是使用大O的渐进表示法来表示
用户的输入空间以及用户要求的输出空间都不算是我们额外开辟的空间
比如说上面的选择排序其C++完整代码如下
void selectionsort(int* arr, int size) { // assert assert(arr); // 还是一样 i控制多少次 j控制每一次的选择排序 int i = 0; int j = 0; int maxi = 0; int tmp = 0; for ( i = 0; i < size-1; i++) { for (j = 0; j < size - 1 - i; j++) { if (arr[j]>arr[maxi]) { maxi = j; } } tmp = arr[size - 1 - i]; arr[size - 1 - i] = arr[maxi]; arr[maxi] = tmp; } }
除了用户提供给我们的数组之外 我们还额外开辟了四个变量 这是常数个变量 所以说这个算法的空间复杂度是O(1)
给定一个数组 要求统计数组里面每个数字出现的次数
我们看这个题目第一时间想到的肯定是使用map来创建一个数字-次数的映射
它的最差情况就是数组中的每个数字都不一样 此时我们要开辟的map映射的数量就是n个
所以说该题目的这种解法的空间复杂度都是O(N)
如何比较两个算法的优劣
一般来说我们比较两个算法的优劣都是先比较时间复杂度
假设有AB两个算法 A算法的时间复杂度是N的平方 B算法的时间复杂度是N
此时我们就可以说B算法比A算法更加优秀
但是如果说A B算法的时间复杂度都是N 此时我们就要开始比较空间复杂度 比较方式同上
在空间复杂度都相同的情况下我们就不比较常数项了
因为在单次的运算中 每种运算所需要的时间就是不同的
比如说位运算就是跑的比加运算要快 加运算就是跑的比除运算要快
所以说我们到这个阶段一般会使用大样本的数据直接来测时间
面试 竞赛中的算法最优解是什么意思？
一般来说我们在设计一个算法最优解的时候首先要考虑的就是这个算法的时间复杂度
在时间复杂度最低的基础上尽可能的去降低它的空间复杂度
需要注意的是 我们比较算法时一般不比较常数项的大小 具体原因可以参考上面的内容
如果说两个算法的时空复杂度都一样 我们可以认为这两个算法一样优秀
常见的时空复杂度及排名
O(1) > O(logN) > O(N) > O(N*logN) > O(N^2)
