侧边栏壁纸
博主头像
码森林博主等级

一起走进码森林,享受编程的乐趣,发现科技的魅力,创造智能的未来!

  • 累计撰写 145 篇文章
  • 累计创建 73 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

算法基础(1):评价算法优劣的核心指标

码森林
2022-01-10 / 0 评论 / 0 点赞 / 253 阅读 / 2,317 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-01-10,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1、评价算法优劣的核心指标

时间复杂度(流程决定)

额外空间复杂度(流程决定)

常数项时间(实现细节决定)

2、时间复杂度

2.1、时间复杂度如何估算?

1. 想象该算法流程所处理的数据状况,按照最差的情况统计计算。
2. 把整个流程拆分成一个个基本动作,保证每个动作都是常数时间的操作。
3. 动作求和,看计算表达式结果。
4. 当完成了表达式的建立,只要把最高阶项留下即可。低阶项都去掉,高阶项的系数也去掉。

2.2、什么是按照最差的情况统计计算?

比如插入排序过程中,我们知道每次都需要把局部进行重新排序,那最好的情况是这个需要排序的数据是已经排好序的,那么我们的时间复杂度就为O(1),但是我们不能因为这个就说插入排序的时间复杂度是O(N),我们要考虑的是最差的情况,最坏的情况是这个需要排序的数据的倒序的,那么我们的时间复杂度就是O(N²)。

2.3、什么是常数时间的操作?

如果一个操作的执行时间不以具体样本量为转移,每次执行时间都是固定时间。称这样的操作为常数时间的操作。

2.4、常见的常数时间操作有哪些?

1. 常见的算术运算(+、-、*、/、% 等)。
2. 常见的位运算(>>、>>>、<<、|、&、^等)。
3. 赋值、比较、自增、自减操作等。
4. 数组寻址操作(如取数组的第N位数据)。

总之,执行时间固定的操作都是常数时间的操作。
反之,执行时间不固定的操作,都不是常数时间的操作,如 LinkedList 的 get() 操作。

2.5、动作求和,看计算表达式结果

这里需要我们把一个流程拆分成一个个基本动作,然后将整个过程求和。这里我们举例进行说明:

选择排序

过程:
arr[0~N-1]范围上,找到最小值所在的位置,然后把最小值交换到0位置。 
基本表达式为:(N-1)*(查询数据+比较数据)+1  #参数说明(n-1)表示需要进行(n-1)次的查询数据和比较数据,因为查询和比较是两个常数项操作,所以这里可以进步抽象为(N-1)*2 +1, 最后系数1是交换位置,下面同理。

arr[1~N-1]范围上,找到最小值所在的位置,然后把最小值交换到1位置。
基本表达式为:(N-2)*2 +1。

arr[2~N-1]范围上,找到最小值所在的位置,然后把最小值交换到2位置。
基本表达式为:(N-3)*2 +1。
…
arr[N-2~N-1]范围上,找到最小值位置,然后把最小值交换到N-1位置。
基本表达式为:2+1。

估算:
很明显,如果arr长度为N,每一步常数操作的数量,如等差数列一般。
所以,总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)。

所以选择排序的时间复杂度为O(N²)。

冒泡排序

过程:
在arr[0~N-1]范围上,arr[0]和arr[1],谁大谁来到1位置;arr[1]和arr[2],谁大谁来到2位置…arr[N-2]和arr[N-1],谁大谁来到N-1位置。
基本表达式为:(N-1)*(查询数据+比较数据)+(交换数据)*N

在arr[0~N-2]范围上,重复上面的过程,但最后一步是arr[N-3]和arr[N-2],谁大谁来到N-2位置。

在arr[0~N-3]范围上,重复上面的过程,但最后一步是arr[N-4]和arr[N-3],谁大谁来到N-3位置。
…
最后在arr[0~1]范围上,重复上面的过程,但最后一步是arr[0]和arr[1],谁大谁来到1位置。


估算:
很明显,如果arr长度为N,每一步常数操作的数量,依然如等差数列一般。
所以,总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)。

所以冒泡排序的时间复杂度为O(N²)。

插入排序

过程:
想让arr[0~0]上有序,这个范围只有一个数,当然是有序的。
想让arr[0~1]上有序,所以从arr[1]开始往前看,如果arr[1]<arr[0],就交换。否则什么也不做。
…
想让arr[0~i]上有序,所以从arr[i]开始往前看,arr[i]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动。
最后一步,想让arr[0~N-1]上有序, arr[N-1]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动。

2.6、如何确定算法流程的时间复杂度?

当完成了表达式的建立,只要把最高阶项留下即可。低阶项都去掉,高阶项的系数也去掉。

即为:O(忽略掉系数的高阶项)

如 a*(N²) + b*N + c,复杂度即为O(N²)

3、额外空间复杂度

概念:在实现算法流程的过程中,需要开辟一些空间来支持的算法流程。

理解:
作为输入参数的空间,不算额外空间。

作为输出结果的空间,也不算额外空间。

因为这些都是必要的、和现实目标有关的,所以都不算。

但除此之外,你的流程如果还需要开辟空间才能让你的流程继续下去,这部分空间就是额外空间。

如果你的流程只需要开辟有限几个变量,额外空间复杂度就是O(1)。

4、常数项时间

其实,算法中重要的凭据点是时间复杂度,只有当时间复杂度相当,这个时候才会来考虑常数项时间。但是实际中,我们并不会直接去分析常数项。

原因有两个:

  1. 常数项的操作都是固定的,但是却又快慢之分,比如我在常数项的操作中,位运算会比普通的加减乘除快。
  2. 理论分析,你需要分析的过程非常多。因为已经具体到细节部分了。所以直接交给实验测试下,就知道优劣了,实践是检验真理的唯一标准。

5、小结

一般情况下,认为解决一个问题的算法流程,在时间复杂度的指标上,一定要尽可能的低,先满足了时间复杂度最低这个指标之后,使用最少的空间的算法流程,叫这个问题的最优解。

一般说起最优解都是忽略掉常数项这个因素的,因为这个因素只决定了实现层次的优化和考虑,而和怎么解决整个问题的思想无关。

0

评论区