[数据结构与算法]评估算法的优劣指标-时间复杂度-空间复杂度-常数操作

一 、时间复杂度

1 看常数操作

????????常数操作算O（1）

????????常见的算术运算（+、-、*、/、% 等）

????????常见的位运算（>>、>>>、<<、|、&、^等）

????????赋值、比较、自增、自减操作等

????????数组寻址操作

????????常数时间操作

????????????????数组-按地址偏移量直接命中 这个就是O（1）

????????非固定时间操作

????????????????链表-需要挨个寻址，这个就不是常数时间操作就是O（N）

2 算法最差情况的复杂度是这个算法的复杂度

????????两层循环，第二层循环是第一层的 i-1 次 这个是等差数列，最后转换成式子? a * n^2 +b * n 这里时间复杂度只看最高阶项部分n^2 所以时间复杂度是O（N^2）

3 例子

排序算法 算时间复杂度

冒泡? O（N^2） 任何情况不变

????????循环数组每个数

????????循环N-1 做交换冒泡

插入排序 O（N^2） 在有序情况下是O（n） 但是时间复杂度O只看最不好的情况

????????循环数组每个

????????N-1 这个数向前比较如果小于就交换

选择 排序 O（N^2） 比冒泡号，因为空间换时间，交换最多只有N次

????????循环数组每个

????????循环n-1个 找到最大的记录下标志，最后与i做交换然后i++

二 、 额外空间复杂度（流程决定）

例1 一个数组 算总和 需要一个变量 来记录sum值

什么是额外空间？

数组开辟的空间，是原始数据，不算额外空间。

需要计算结果而开辟的空间，而不是原始数据，这样开辟的空间是额外空间。

例2 ??一个数组 算每个数出现次数 需要一个map来记录

什么是额外空间复杂度

例1的额外空间复杂度是O（1） 因为他不会随着初始数据变化而增长

例2 的额外空间复杂度是O（N）因为他会随着初始数据变化而增长

总结：算法入输出的空间都不是额外空间！

三、 常数项的时间

比较常数操作 多少

例如 插入排序 1234567 是O（n）

例如 冒泡 1234567 是O（n^2）

这里插入比冒泡少了比较和交换的常数项操作

比较常数操作 优劣

?排序算法 交换操作? 一个是用 + - 进行 一个是用 ^ 进行

常数操作^ 比 + - 快 因为是位运算

如何PK常数项时间？

直接测试

四 、PK算法哪个最优

1 先满足时间复杂度最优

2 再满足空间复杂度最优

3 常数项因素 不算做PK最优（跟算法思想没关系，是细节方面）

五、排名从好到差：

O(1)??

O(logN)??

O(N)??

O(N*logN)??

O(N^2)?? O(N^3)?? …?? O(N^K)

O(2^N)?? O(3^N)?? …?? O(K^N)

O(N!)