10-简单时间复杂度分析

简单时间复杂度分析

通常见到的 $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()，也就是说总共操作（包括扩容和添加数据）了 $2n+1$ 次（前面数组未扩容和扩容后总共可以使用的addLast()操作），用 $总共操作/未扩容添加操作$ ，即 $(2n+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_2n)$ ，复杂度要忽略参数所以最终的复杂度是 $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 )$ ），既可以做到空间复杂度和时间复杂度都有很大的提升