时间复杂度和空间复杂度

时间复杂度

常数时间的操作

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

总之，执行时间固定的操作都是常数时间的操作。
反之，执行时间不固定的操作，都不是常数时间的操作。

估算时间复杂度

1. 想象该算法流程所处理的数据状况，要按照最差情况来。
2. 把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作。
3. 如果数据量为N，看看基本动作的数量和N是什么关系。
4. 当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉。
   记为:O(忽略掉系数的高阶项)

比如：常数时间的操作的次数为xN^2+yN+z,则时间复杂度为O(N^2)

常见的时间复杂度

O(1)、O(N)、O(logN)、O(N*logN)、O(N^2)、O(N^3)、O(N^k)、O(2^N)、O(3^N)、O(k^N)、O(N!)

额外空间复杂度

你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。
作为输入参数的空间,不算额外空间。
作为输出结果的空间，也不算额外空间。
因为这些都是必要的、和现实目标有关的。所以都不算。
但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。

最优解

一般情况下，认为解决一个问题的算法流程,在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，使用最少的空间的算法流程，叫这个问题的最优解。
一般说起最优解都是忽略掉常数项这个因素的,因为这个因素只决定了实现层次的优化和考虑，而和怎么解决整个问题的思想无关。

异或运算

1. 不申请额外的存储空间，交换两个整数的值：

   let a = 1
   let b = -1
   a = a ^ b
   b = a ^ b
   a = a ^ b
   console.log(a) //-1
   console.log(b) //1

2. 一个数组中有一个数出现了奇数次，其余的数都出现偶数次，找出那个数：

   let arr = [1,3,2,1,4,3,3,4,2]
   let eor = 0
   arr.forEach(value => {
     eor ^= value
   })
   console.log(eor) //3

参考视频