exercise

exercise…

simple record

const a = [1, 2, ...[]];
console.log(a); // [1,2]

判断循环就用快慢指针

用 hash 集合反复检查其中是否存在某数字

-16 的 2 进制的补码是 15
所以-2 的 31 次方的补码是 2 的 31 次方-1

时间复杂度

O(1) 最低的时空复杂度 耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。 哈希算法就是典型的 O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标

时间复杂度为 O(n)—线性阶，就代表数据量增大几倍，耗时也增大几倍。

时间复杂度 O(n^2)—平方阶, 就代表数据量增大 n 倍时，耗时增大 n 的平方倍，这是比线性更高的时间复杂度

时间复杂度 O(logn)—对数阶，当数据增大 n 倍时，耗时增大 logn 倍(这里的 log 是以 2 为底的，比如，当数据增大 256 倍时，耗时只增大 8 倍，是比线性还要低的时间复杂度)。二分查找就是 O(logn)的算法，每找一次排除一半的可能，256 个数据中查找只要找 8 次就可以找到目标。

时间复杂度 O(nlogn)—线性对数阶，就是 n 乘以 logn，当数据增大 256 倍时，耗时增大 256*8=2048 倍。这个复杂度高于线性低于平方。归并排序就是 O(nlogn)的时间复杂度。

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) < O(n^n)

1. 时间复杂度为 O (1)，代码只被执行一次。
2. 时间复杂度为 O (n)，比如常见的遍历算法。 也就是一个 for 循环的时间复杂度。
3. O(n^2)就是嵌套 for 循环，就是两个 for 循环，是不是相当于运行了 n*n 次。比如冒泡和选择排序。
4. 再比如 O (logn)，（ log 是以 2 为底）。二分搜索就是 O (logn) 的算法，每找一次排除一半的可能。
5. O (nlogn) 同理，就是 n 乘以 logn，归并排序就是 典型的例子。

空间复杂度

可以类比于时间复杂度

1. O(1)单个变量所占的空间永远为 1

2. O(n)数组里面有 n 个值，占用了 n 个内存单元

3. O(n^2)可以想象为一个正方形，边长为 n，存储了 n 的二次方个变量