乐趣区

关于复杂度:常见排序算法及复杂度

jiezi

1. 常见算法复杂度

大 O 加上（）的模式，外面其实包裹的是一个函数 f(),O（f()）, 指明某个算法的 “耗时 / 耗空间”与“数据增长量”之间的关系。其中的 n 代表输出数据的量。

1.1. O(1)

1. 解释

最低复杂度，常量值。也就是“耗时 / 耗空间”与“数据增长量”无关，无论输出数据增大多少倍，“耗时 / 耗空间”都不变。

2. 举例

哈希算法就是典型的 O(1)工夫复杂度算法，例如 HashMap、布隆过滤器等哈希算法的利用，无论数据规模多大，在计算出 hash key 的值之后，都能够一次性找到指标（不思考哈希抵触的话）。

1.2. O(n)

1. 解释

数据量增大几倍，耗时也增大几倍。

2. 举例

例如：最常见的遍历算法，遍历一次所有值，找出其中的最大值。

1.3. O(n^2)

1. 解释

对 n 个数排序，须要扫描 n^2 次。

2. 举例

例如：冒泡排序法、抉择排序法等。因为该算法都是 2 层循环，第一层循环遍历 n-1 趟，第二层循环遍历 n-i 趟（i 递增）。

1.4. O(logn)

1. 解释

当数据增大 n 倍时，耗时增大 logn 倍。

这里 log 是以 2 为底。比方：log256=8

2. 举例

二分查找法就是 O(logn) 的算法，每找一次就排除个别的可能性，256 条数据中只需查找 8 次就能够。

1.5. O(nlogn)

1. 解释

当数据增大 n 倍时，耗时增大 n 乘以 logn 倍。例如当数据增大 256 倍，耗时增大 256*8 倍。

这个复杂度高于线性 O(n)，低于平方 O(n^2)。

2. 举例

归并排序法、疾速排序法的工夫复杂度就是 O(nlogn)。

2. 排序算法复杂度

网上看到这张图：

2.1. 冒泡排序为啥 O(n^2)

冒泡排序法遍历的次数：

  • 总层数：n−1
  • 每层遍历次数：n−i（i 在 1 ~ n 递增）
  • 可基于 ∑i 求和，计算出总次数：n(n−1)/2=n^2/2 - n/2

既然是 n^2/2 - n/2，为什么说工夫复杂度是 O(n^2) 呢？因为咱们常说的复杂度不是精确的值，而是当数据量收缩时，随之工夫收缩的模型。当 n 趋向于无限大时，n^2/2 – n/2 也就趋向于 n^2。

2.2. 疾速排序为啥 O(nlogn)

1. 算法原理

  1. 从待排序的 n 个记录中任意选取一个记录（通常选取第一个记录）为分区规范;
  2. 把所有小于该排序列的记录挪动到右边，把所有大于该排序码的记录挪动到左边，两头放所选记录，称之为第一趟排序；
  3. 而后对前后两个子序列别离反复上述过程，直到所有记录都排好序。

2. 稳定性

不稳固排序。

3. 工夫复杂度

O（nlog2n）至 O(n2)，均匀工夫复杂度为 O（nlgn）。

4. 最好的状况

是每趟排序完结后，每次划分使两个子文件的长度大抵相等，工夫复杂度为 O（nlog2n）。

  • 总层数：logn，因为假如每次划分都使两个子文件的长度大抵相等，那么划分 logn 次后即无奈持续划分。
  • 每层遍历次数：n-i
  • 总次数：同冒泡排序法，当 n 趋于无限大，总次数为 nlogn

5. 最坏的状况

是待排序记录曾经排好序。

  • 第一趟通过 n - 1 次比拟后第一个记录放弃地位不变，并失去一个 n - 1 个元素的子记录；
  • 第二趟通过 n - 2 次比拟，将第二个记录定位在原来的地位上，并失去一个包含 n - 2 个记录的子文件。

顺次类推，这样总的比拟次数是：
Cmax=∑i=n−1(n−i)=n(n−1)/2=O(n2)

6. 复杂度总结

通过最好、最坏的状况比照，每层遍历的次数差距不大，差距大在层数。

这里层数的计算，理论等同于二叉树的高度，二叉树查找算法的复杂度就 O(logn)，咱们就拿它当二叉树来看。

如果二叉排序树的子树间的高度相差太大，就会让二叉排序树操作的工夫复杂度降级为 O(n)，为了防止这一状况，为最坏的状况做筹备，就呈现了均衡二叉树。

总结：

  • 当二叉树趋于均衡，也就是快排的每次划分比拟均等，层数趋于 logn，快排复杂度趋于 O(nlogn)。
  • 当二叉树不够均衡，甚至都成一条直线了，层数趋于 n，快排复杂度趋于 O(n^2)。

3. 数据结构：堆

3.1. 定义

定义

堆是应用数组实现，基于齐全二叉树的数据结构。

齐全二叉树

  • 二叉树: 每个非叶子节点最多有两个分支节点。
  • 满二叉树: 每个非叶子节点都有两个子节点。
  • 齐全二叉树: 最初一层的最初一个节点的父节点不满足满二叉树之外，其它非叶子节点都满足满二叉树。

最小堆与最大堆

  • 最大堆：是一个齐全二叉树，所有的父节点都大于或等于它的左右孩子节点。
  • 最小堆：是一个齐全二叉树，所有的父节点都小于或等于它的左右孩子节点。

后一半是叶子节点

堆的前一半是非叶子节点，后一半是叶子节点。

因为叶子节点排在数组最初，而假如某叶子节点地位为 k，对应父节点为 k/2。

3.2. 堆操作

二叉堆尽管是一个齐全二叉树，然而它的存储形式并不是链式存储，而是顺序存储，它所有的节点都存储在数组中。

  1. 它是齐全二叉树，除了树的最初一层结点不须要是满的，其它的每一层从左到右都是满的，如果最初一层结点不是满的，那么要求左满右不满。

  2. 它通常用数组来实现。并且从索引 1 开始存储，即索引 0 间接废除。具体方法就是将二叉树的结点依照层级程序放入数组中，根结点在地位 1，它的子结点在地位 2 和 3，而子结点的子结点则别离在地位 4, 5 , 6 和 7，以此类推。

    如果一个结点的地位为 k，则它的父结点（根节点没有父结点）的地位为[k/2]，而它的两个子结点的地位则别离为 2k 和 2k+1。这样，在不应用指针的状况下，咱们也能够通过计算数组的索引在树中高低挪动。

  3. 每个结点都（大于或小于）等于它的两个子结点。这里要留神堆中仅仅规定了每个结点（大于或小于）等于它的两个子结点，但这两个子结点的程序并没有做规定，跟二叉查找树是有区别的。
  4. 上述提到的结点须要（大于或小于）等于它的两个子节点，是依据堆的类别来判断的。将根节点最大的堆叫做最大堆或大根堆，结点须要大于等于它的两个子结点；根节点最小的堆叫做最小堆或小根堆，结点须要小于等于它的两个子结点。

1. 堆的插入

堆是用数组实现数据元素的存储的，咱们往数组中从索引 1 处开始，顺次往后存放数据，然而堆中对元素的程序是有要求的，每一个结点的数据要（大于或小于）等于它的两个子结点的数据，所以每次插入一个元素，都会使得堆中的数据程序变乱，这个时候咱们就须要通过一些办法让方才插入的这个数据放入到适合的地位。

如果往堆中新插入元素，咱们只须要一直的比拟新结点 a[k] 和它的父结点 a[k/2] 的大小，而后依据后果实现数据元素的替换，就能够实现堆的有序调整。这里就设计到堆的上浮操作，等会再细谈。

2. 删除根节点

由堆的个性咱们能够晓得，索引 1 处的元素，也就是根结点。当咱们把根结点的元素删除后，堆的程序就乱了，那么咱们应该怎么删除呢？

思路：

  • 替换根节点与最初一个元素
  • 把开端的根节点删除
  • 对新的根节点进行下沉操作，使之处于正确的地位

当须要删除最值时，只须要将最初一个元素放到索引 1 处，并一直的拿着以后结点 a[k] 与它的子结点 a[2k]和 a[2k+1] 中的（较大者或较小者，依据最大堆、最小堆判断）替换地位，即可实现堆的有序调整。

3. 上浮操作

最大堆的上浮思路：

  1. 确定须要上浮元素的下标 k
  2. 当 k > 1 时，比拟 item[k] 与 item[k / 2] 的大小
    2.1. 若 item[k] > item[k / 2]，替换两者地位，k = k / 2
    2.2. 若 item[k] <= item[k / 2]，上浮完结

最小堆的上浮思路：

  1. 确定须要上浮元素的下标 k
  2. 当 k > 1 时，比拟 item[k] 与 item[k / 2] 的大小
    2.1. 若 item[k] < item[k / 2]，替换两者地位，k = k / 2
    2.2. 若 item[k] >= item[k / 2]，上浮完结

4. 下沉操作

最大堆的下沉思路：

  1. 确定须要下沉元素的下标 k
  2. 当 k 2 <= N（N 为堆中元素个数）时，比拟 item[k] 与 max{item[k 2]，item[k 2 + 1]} 的大小，并记录 item[k 2]，item[k * 2 + 1] 较大值的下标 maxIndex
    2.1. 若 item[k] < item[maxIndex]，替换两者地位，k = maxIndex
    2.2. 若 item[k] >= maxIndex，下沉完结

最小堆的下沉思路：

  1. 确定须要下沉元素的下标 k
  2. 当 k 2 <= N（N 为堆中元素个数）时，比拟 item[k] 与 min{item[k 2]，item[k 2 + 1]} 的大小，并记录 item[k 2]，item[k * 2 + 1] 较小值的下标 minIndex
    2.1. 若 item[k] > item[maxIndex]，替换两者地位，k = minIndex
    2.2. 若 item[k] <= maxIndex，下沉完结

5. 堆的结构

堆的结构，最直观的想法就是另外再创立一个新数组，而后从左往右遍历原数组，每失去一个元素后，增加到新数组中，并通过上浮，对堆进行调整，最初新的数组就是一个堆。
上述的形式尽管很直观，也很简略，然而咱们能够用更聪慧一点的方法实现它。创立一个新数组，把原数组 [0 ~ length -1] 的数据拷贝到新数组的 [1 ~ length]处，再从新数组长度的一半处开始往 1 索引处扫描（从右往左），而后对扫描到的每一个元素做下沉调整即可。

6. 堆的排序

实现步骤：

  1. 结构堆
  2. 失去堆顶元素，这个值就是最大值
  3. 替换堆顶元素和数组中的最初一个元素，此时所有元素中的最大元素曾经放到适合的地位
  4. 对堆进行调整，从新让除了最初一个元素的残余元素中的最大值放到堆顶
  5. 反复 2~4 这个步骤，直到堆中剩一个元素为止

对于堆的结构，上述曾经谈到，对结构好的堆，咱们只须要做相似于堆的删除操作，就能够实现排序。

  1. 将堆顶元素和堆中最初一个元素替换地位；
  2. 通过对堆顶元素下沉调整堆，把最大的元素放到堆顶(此时最初一个元素不参加堆的调整，因为最大的数据曾经到了数组的最左边)
  3. 反复 1~2 步骤，直到堆中剩最初一个元素。

3.3. 优先队列

队列是一种先进先出 (FIFO) 的数据结构，但有些状况下，操作的数据可能带有优先级，个别出队列时，可能须要优先级高的元素先出队列。

此时，数据结构应该提供两个最根本的操作，一个是返回最高优先级对象，一个是增加新的对象。这种数据结构就是 优先级队列(Priority Queue)。

优先级队列实现了 Queue 接口。

JDK1.8 中的 PriorityQueue底层应用了 堆的数据结构。

优先队列依照其作用不同，能够分为以下两种：

  1. 最大优先队列：能够获取并删除队列中最大的值，基于最大堆实现。
  2. 最小优先队列：能够获取并删除队列中最小的值，基于最小堆实现。

4. 问题考查

这里转述一个问题：

如果有 10 亿条数据，心愿找出最大的 10 条，最优计划有哪些？具体工夫复杂度是多少？

咱们能够用 n 代替 1 亿，k 代替 10，下列有三种解法作为参考。

1. 解法一：O(nlogn)

看到取最大 / 小数，预计很多人首先想到的，就是通过 xx 排序法做个排序，而后再取值。而后 疾速排序法 相对而言复杂度最低，就由此答案。

整个过程的复杂度也就是疾速排序法的复杂度：O(nlogn)。

2. 解法二：O(nk)

第一种解法最大的问题在于，尽管疾速排序法对整体排序的复杂度最好，但我只须要获取最大的 10 条数据，却破费性能，对 10 亿条数据都做了排序。

因而这就诞生了第二种解法，就应用冒泡排序法、抉择排序法等，只须要 10 次遍历，就能选出最大的 10 条数据。

每次遍历须要 n- i 次，因为 n 有 10 亿，i 最大仅为 10，那么整个过程的复杂度为：O(n*10)。

3. 解法三：O(nlogk)

接下来换一种思路：

  1. 咱们先取前 10 条数据保护一个汇合，只找出这 10 条数据中的最小值。
  2. 而后从第 11 条数据开始顺次遍历，如果第 i 条数据大于汇合内的最小值，那么就用这第 i 条数据替换汇合内的最小值，并且对汇合内的数据从新排序。
  3. 当遍历到最初一条数据，这汇合内的数据就是最大的 10 条数据了。

接下来算一下复杂度：

  • 遍历次数：n-10，约为 n。

  • 找到汇合内的最小值：

    • （1）如果是间接遍历，复杂度为 O(10)；
    • （2）如果咱们保护最小堆，复杂度为 O(log10)。显著最小堆复杂度更低。
  • 总最小工夫复杂度：O(nlog10)
退出移动版