Rayjun

算法简明教程

复杂度分析

通过直接跑算法得到的执行时间和占用内存大小的统计称之为事后统计法，这种方法有很大的局限性：

  • 测试结果非常依赖测试环境
  • 测试结果受数据规模的影响很大

大 O 复杂度表示法可以不用具体的数据进行测试，就可以粗略的估算算法的执行效率。

时间复杂度

所有代码的执行时间 $T(n)$ 与每行代码执行的执行次数 n 成正比

$$T(n) = O(f(n))$$

这就是大 O 时间复杂度表示法，但这个方法实际上并不代表代码真正的执行时间，而是代表代码执行时间随数据规模增长的变化趋势，也称之为渐进时间复杂度。

如何具体的分析算法的时间复杂度：

  • 只关注循环执行次数最多的一段代码
  • 加法法则：总复杂度等于量级最大的那段代码的复杂度
  • 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见的时间复杂度：

  • 常量阶： $O(1)$
  • 对数阶： $O(logn)$
  • 线性阶： $O(n)$
  • 线性对数阶： $O(nlogn)$
  • 平方、立方、k次方阶： $O(n^2)$ $O(n^3)$ $O(n^k)$
  • 指数阶： $O(2^n)$
  • 阶乘阶： $O(n!)$

最好时间复杂度：最理想的情况下，执行这段代码的时间复杂度
最坏时间复杂度：最坏的情况下，执行这段代码的时间复杂度
平均时间复杂度：加权平均复杂度或者期望时间复杂度
摊还时间复杂度：把一次复杂操作的时间平均到 n - 1 次简单操作上，所以整体还是简单操作的时间复杂度

空间复杂度

表示算法的存储空间与数据规模之间的增长关系，通常用到的空间复杂度有 $O(1)$、$O(N)$、$O(N^2)$。

递归

可以使用递归方法解决问题的三个条件:

  • 一个问题可以分解为多个问题的解
  • 这个问题与分解之后的子问题，除了数据规模不同，其他的完全一样
  • 存在递归终止条件

编写递归代码时，需要找出递推公式，而不要去想每一层递归的细节

递归的问题：

  • 警惕出现堆栈溢出
  • 警惕重复计算

排序

排序算法的衡量标准:

  • 排序算法的执行效率
    • 最好情况、最坏情况、平均时间复杂度
    • 时间复杂度的系数、常数、低阶
    • 比较次数和交换次数
  • 排序算法的内存消耗
  • 排序算法的稳定性

冒泡排序

时间复杂度：$O(n^2)$
最好时间复杂度： $O(n)$
最坏时间复杂度： $O(n^2)$
空间复杂度: $O(1)$ 原地排序
稳定性：稳定
数据范围： 适合小规模数据

插入排序

时间复杂度：$O(n^2$
最好时间复杂度：$O(n)$
最坏时间复杂度：$O(n^2))$
空间复杂度：$O(1)$
稳定性: 稳定
数据范围： 适合小规模数据

选择排序

时间复杂度：$O(n^2)$
最好时间复杂度: $O(n^2)$
最坏时间复杂度: $O(n^2)$
空间复杂度: $O(1)$
稳定性: 不稳定
数据范围: 适合小规模数据

归并排序

归并排序是自下而上的排序方法，所以要先分区再处理数据，而快排则是相反的，需要先处理数据，再来分区。

时间复杂度: $O(nlogn)$
最好时间复杂度: $O(nlogn)$
最坏时间复杂度: $O(nlogn)$
空间复杂度: $O(n)$
稳定性: 稳定
数据范围: 适合大规模数据

快速排序

快速排序进行分区时，使用的方式与选择排序有点类似，首先选择这个分区的最后一个值作为分区点的值。就是将小于分区点的元素都放在数组的前面，最后把分区点移到中间，后面的元素就都大于分区点，分区也就完成了。

利用快速排序可以在 $O(N)$ 的时间复杂度内找出一个无序数组中第 K 大的元素。

时间复杂度：$O(nlogn)$
最好时间复杂度: $O(nlogn)$
最坏时间复杂度: $O(nlogn)$
空间复杂度: $O(1)$
稳定性: 不稳定
数据范围: 适合大规模数据

桶排序

桶排序的核心思想是将要排序的数据分别分到几个桶里面，然后对桶里面的数据进行单独的排序。桶内排序完成之后，将每个桶内的元素按照顺序取出，得到的结果就是有序的。

时间复杂度：$O(n)$
最好时间复杂度: $O(n)$
最坏时间复杂度: $O(nlogn)$
空间复杂度: $O(n)$
稳定性: 稳定
数据范围： 适合大规模数据

计数排序

时间复杂度：$O(n)$
最好时间复杂度: $O(n)$
最坏时间复杂度: $O(nlogn)$
空间复杂度: $O(n)$
稳定性: 稳定
数据范围： 适合数据范围不大的场景

基数排序

基数排序对要排序的数据是有要求的，需要可以分割出独立的‘位’来进行比较。
时间复杂度：$O(n)$
最好时间复杂度: $O(n)$
最坏时间复杂度: $O(nlogn)$
空间复杂度: $O(n)$
稳定性: 稳定
数据范围： 适合数据范围不大的场景

堆排序

时间复杂度: $O(NlogN)$
最好时间复杂度: $O(NlogN)$
最坏时间复杂度: $O(NlogN)$
空间复杂度: $O(1)$
稳定性：不稳定
适用范围：适用于数据处在动态变化中的数据

二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为一半，直到找到要查找的元素，或者区间缩小为0。

时间复杂度: $O(logN)$
空间复杂度: $O(1)$

二分查找对于数据有着严格的要求，数据必须存储在连续内存中，而且必须有序。

二分查找算法有很多的变体：

  • 查找第一个值等于给定值的元素
  • 查找最后一个值等于给定值的元素
  • 查找第一个大于等于给定值的元素
  • 查找最后一个小于等于给定值的元素

字符串匹配算法

字符串匹配算法在各个编程语言中都有实现。

字符串匹配算法有很多实现:

  • BF: 暴力匹配算法（朴素匹配算法）
  • RK: 在 BF 的基础之上引入哈希算法来提高效率
  • BM: 通过一次多移动位数来提高效率
  • KPM: 引入了动态规划的思想

四种算法思想

贪心算法

对一组数据，定义了期望值和限制值，希望从中选出几个数据，在满足限制值得情况下，期望值最大，这个时候就可以使用贪心算法。

贪心算法应用有：

  • 霍夫曼编码
  • 最小生成树算法
  • Dijkstra 最短路径算法

分治算法

分治算法的关键在于将原问题分解为 n 个与原问题结构相似的子问题，然后递归的解决这些子问题，最后合并成一个结果，就是分而治之。

分治算法的应用有：

  • MapReduce
  • 处理海量数据
  • 归并排序

回溯算法

回溯的思想有点类似于枚举搜索。为了让枚举的过程有序，会将枚举的过程分成多个阶段，每个阶段都会选择一个路径，但路径走不通时，就会退回到上一个阶段，选择另一条路径。

回溯算法的应用有：

  • 深度优先搜索
  • 八皇后
  • 0-1 背包
  • 图的着色
  • 旅行商问题
  • 数独
  • 全排列
  • 正则表达式

动态规划

动态规划一般用来解决最优问题。可以用动态规划解决的问题一般有三个特征:

  • 最优子结构：问题的最优解当中包含子问题的最优解，也就是说可以通过子问题的最优解来推断问题的最优解
  • 无后效性：在推导后续的问题时，只关注当前阶段的状态值，而不关心这个状态是怎么推导出来的。而且某个阶段的状态确定后，就不会收后续阶段的影响。
  • 重复子问题

动态规划的应用有：

  • 爬楼梯
  • 0-1 背包
©2024 Rayjun    PowerBy Hexo