00-时间复杂度

时间复杂度分析

通常见到的 $O (1)$ 、 $O (n)$ 、 $O (\log _n)$ 、 $O (n\log _n)$ 、 $O (n^2)$ 的描述时间复杂度的方式，简单的说其实是描述的是算法的运行时间和输入数据之间的关系，比如 $O (n)$ ：输入数据与时间是呈线性关系的（也就是一元函数，忽略了一些参数，因为这些参数难以计算甚至无法计算），输入数据越多越耗时； $O (n^2)$ ：输入数据与时间呈指数关系（也就是幂函数，当参数远远小于 $O (n)$ 时间虽然可能会比 $O (n)$ 少，但是时间复杂度是按照当 n 趋向无穷时的情况，所以即使可能有一个低阶的项也会因为趋向去穷会被忽略掉，即渐近时间复杂度）

数组时间复杂度分析

添加操作

addLast ()：不需要向后挪动元素，无需遍历数组元素，复杂度是 $O (1)$
addFirst ()：需要将所有元素向后挪动，遍历所有数组元素，复杂度是 $O (n)$
add ()：根据索引位置插入元素，因为插入位置可能靠前可能靠后，平均下来复杂度是 $O (n/2)$ ，复杂度要忽略参数所以最终的复杂度是 $O (n)$
若数组满了的情况下会扩容数组，调用resize ()方法，遍历整个数组元素，复杂度是 $O (n)$

综合的考虑（最坏的情况），复杂度是 $O (n)$

删除操作

removeLast ()：不需要向前挪动元素，无需遍历数组元素，复杂度是 $O (1)$
removeFirst ()：需要将所有的元素向前挪动，遍历所有数组元素，复杂度是 $O (n)$
remove ()：根据索引位置删除元素，因为删除位置可能靠前可能靠后，平均下来复杂度是 $O (n/2)$ ，复杂度要忽略参数所以最终的复杂度是 $O (n)$
若数组达到一定空闲位置就会缩容数组，调用resize ()方法，遍历整个数组，复杂度是 $O (n)$

综合的考虑（最坏的情况），复杂度是 $O (n)$

修改操作

set ()：只要知道索引就可以修改，不需要遍历数组，复杂度是 $O (1)$
contains ()：根据元素内容来判断是否包含了该元素，需要遍历整个数组，复杂度是 $O (n)$
find ()：根据元素内容获取元素索引，需要遍历整个数组，复杂度是 $O (n)$

综合的考虑，未知索引复杂度是 $O (n)$ ，已知索引复杂度是 $O (1)$

查询操作

get ()：只要知道索引就可以获取指定的元素，不需要遍历数组，复杂度是 $O (1)$
contains ()：根据元素内容来判断是否包含了该元素，需要遍历整个数组，复杂度是 $O (n)$
find ()：根据元素内容获取元素索引，需要遍历整个数组，复杂度是 $O (n)$

综合的考虑，未知索引复杂度是 $O (n)$ ，已知索引复杂度是 $O (1)$

Resize 复杂度分析

在增删中，若只是使用removeLast ()、addLast ()操作时，复杂度是 $O (1)$ ，但是可能会触发扩容或缩容，resize ()的复杂度是 $O (n)$ 所以最坏的情况下就是 $O (n)$ ，但是这显然是不合理的，因为扩容的操作明显要少的很多

均摊复杂度

假设当前数组容量是 n，n+1 次的addLast ()操作才会触发resize ()，也就是说总共操作（包括扩容和添加数据）了 $2 n+1$ 次（前面数组未扩容和扩容后总共可以使用的addLast ()操作），用 $总共操作/未扩容添加操作$ ，即 $(2 n+1)/(n+1)=2$ （n 趋向无穷），也就是说将扩容操作平坦给每次的添加操作，就相当于每次添加操作等于两次的添加操作，按照这样来算的话就是 $O (1)$

复杂度震荡

在单独对addLast ()和removeLast ()分析时的均摊复杂度都是 $O (1)$ ，但是同时考虑时就会出现问题（前提是扩容和缩容的容量和判断一致）；假设数组容量是 n，刚好在临界点反复的添加和删除元素，就会导致数组的使用resize ()方法进行扩容和缩容操作

所以在缩容时不要正好到刚好盛满，并且最好不与扩容的策略一致

单向链表时间复杂度分析

综合来看链表的增删改查操作复杂度都是 $O (n)$ ，但是若仅对链表头部操作则复杂度是 $O (1)$ ，而且不必考虑容量的问题，这点就是对数组来说的优势

添加操作

addLast ()：需要从链表头遍历到链表尾，复杂度是 $O (n)$
addFirst ()：只需要将链表头指向修改，复杂度是 $O (1)$
add ()：根据索引位置插入元素，因为插入位置可能靠前可能靠后，平均下来复杂度是 $O (n/2)$ ，复杂度要忽略参数所以最终的复杂度是 $O (n)$

综合的考虑（最坏的情况），复杂度是 $O (n)$

删除操作

removeLast ()：需要从链表头遍历到链表尾，复杂度是 $O (n)$
removeFirst ()：只需要将链表头指向修改，复杂度是 $O (1)$
remove ()：根据索引位置删除元素，因为删除位置可能靠前可能靠后，平均下来复杂度是 $O (n/2)$ ，复杂度要忽略参数所以最终的复杂度是 $O (n)$

综合的考虑（最坏的情况），复杂度是 $O (n)$

修改操作

set ()：需要遍历整个链表找到要修改的位置，复杂度是 $O (n)$
contains ()：需要遍历整个链表，复杂度是 $O (n)$

综合的考虑（最坏的情况），复杂度是 $O (n)$

查询操作

get ()：需要遍历整个链表找到指定位置元素，复杂度是 $O (n)$
contains ()：需要遍历整个链表，复杂度是 $O (n)$

综合的考虑（最坏的情况），复杂度是 $O (n)$

栈时间复杂度分析

基于动态数组的栈

push ()：等价于addLast ()，（扩容）均摊复杂度是 $O (1)$
pop ()：等价于removeLast ()，（缩容）均摊复杂度是 $O (1)$
其他操作复杂度都是 $O (1)$

基于单向链表的栈

push ()：等价于addLast ()，复杂度是 $O (1)$
pop ()：等价于removeLast ()，复杂度是 $O (1)$
其他操作复杂度都是 $O (1)$

比较不同实现方式的

基于动态数组：
- 有固定容量限制，可能会浪费存储空间
- 在扩容和缩容操作过多时时间复杂度也会随之增大
基于单向链表：
- 没有固定容量限制，不会浪费存储空间
- 在添加节点时是通过new关键字来创建节点，在空间不足时会找可使用的存储空间，这就可能会更加耗时
综上所述，这两种实现方式在性能上并没有特别大的差异，而是与当前的操作和当前操作系统的状态有关系

队列时间复杂度分析

基于动态数组的队列

enqueue ()：等价于addLast ()，均摊复杂度是 $O (1)$
dequeue ()：等价于removeFirst ()，复杂度是 $O (n)$
其他操作复杂度都是 $O (1)$

综合的考虑（最坏的情况），复杂度是 $O (n)$

基于静态数组的循环队列

enqueue ()：直接尾部插入元素，已知索引就是尾部指针，复杂度是 $O (1)$
dequeu ()：直接头部插入元素，已知索引就是头部指针，复杂度是 $O (1)$
其他操作复杂度都是 $O (1)$

综合的考虑，复杂度是 $O (1)$

基于单向链表的队列

enqueue ()：直接尾部插入元素，已知索引就是尾部指针，复杂度是 $O (1)$
dequeu ()：直接头部插入元素，已知索引就是头部指针，复杂度是 $O (1)$
其他操作复杂度都是 $O (1)$

综合的考虑，复杂度是 $O (1)$

树时间复杂度分析

添加操作、删除操作和查询，操作其实和链表一样遍历节点，只不过会将添加元素和当前节点进行比较，近乎可以减少一半无效访问，所遍历的节点最多是当前树的高度（最大深度），也就是说当前复杂度是 $O (h)$ ，h 是当前树的高度

假设当前树是一个满二叉树，第 0 层有一个节点，第二层有 2 个节点，第三层有 4 个节点，依次类推第 h 层就有 $2 ^ h$ ，此时拥有 h 层的满二叉树共拥有 $2 ^ 0+2 ^ 1+...+2 ^ {h-1}$ 个节点，这刚好是个等差数列，根据求和公式 $\frac{a_1 (1-q^n)}{1-q}(其中 n 是项数)$ 得到 $\frac{1*(1-2^h)}{1-2}=2^h-1=n$ ，此时 $h=\log _2 (n+1)$ ，所以复杂度是 $O (\log_2 n)$ ，复杂度要忽略参数所以最终的复杂度是 $O (\log n)$
假设当前树已经退化成一个链表时， $h=n$ ，此时的添加操作、删除操作和查询操作会与链表一样，都是 $O ( n )$

所以大多数情况下树的综合复杂度是 $O (\log n)$ 到 $O ( n )$ 之间的，为了时间复杂度保持在 $O (\log n)$ 就需要采用平衡二叉树

集合和映射时间复杂度分析

基于链表的集合和映射

由于向链表中插入元素时需要遍历整个链表来判断重复元素，所以复杂度是 $O (n)$ ，删除指定元素时也需要遍历整个链表进行比对删除，所以复杂度也是 $O (n)$ ，综合考虑复杂度是 $O ( n )$

基于二分搜索树的集合和映射

树的操作综合复杂度是 $O (\log n)$ 到 $O ( n )$ 之间的的，所以基于二分搜索树实现的集合和映射也是 $O (\log n)$ 到 $O ( n )$ 之间的

堆时间复杂度分析

由于堆是一颗完全二叉树，永远不可能退化成链表，所以堆的增加删除操作都是 $O (\log n)$

哈希表时间复杂度分析

链地址法：当前哈希表大小为 M，若放入 n 个元素后，平均每个位置就是 $n/M$ 个元素，所以若是使用链表存储平均复杂度就是 $O (n/M)$ ，若使用平衡树存储平均复杂度就是 $O (log_{(n/M)})$ ，最坏的情况下全部都哈希冲突时，就和链表、树结构的复杂度一样了，但是大部分情况下不会这样，也就是说现在的时间复杂度和 M 有关系，若 M 设置的合理，使得数据分布的均匀，就可以达到 $O (1)$ 的复杂度，此时 M 应该是一个动态的，根据存储元素的数量的不同而改变（即扩容缩容操作，扩容操作与数组扩容一致均摊复杂度是 $O ( 1 )$ ），既可以做到空间复杂度和时间复杂度都有很大的提升