Table of Contents

常见算法思想

2020-07-28
5 min read
algs

思考过程

遇到问题后常见的思考过程：

直观感受 / 类似问题？ / 举例&简单case / 简化问题 / 画图 / 分解 / 排序&倒序？ / 特殊形式 / 通用算法模式 /

上面所说的通用算法模式指的是回溯、动态规划、分治等方法

  1. 先举例思考暴力算法、然后寻找算法耗时与重复的地方进行优化、再考虑通用算法、再进一步优化
    1. 从时间复杂度的角度上考虑解决办法。思考问题的极限最小运行时间（BCR，base code runtime）
      1. \(O(1)\) 复杂度的算法，例如 hash；\(O(long\ n)\) 复杂度的算法与数据结构有平衡树树、堆或者二分查找；\(O(n)\) / \(O(nlong\ n)\) 复杂度的算法，有桶排序/快排
    2. DEBUG3C 。Exhaustive Search、Backtracking、Decrease-and-Conquer、Divide-and-Conquer、Transform-and-Conquer、Greedy Approach、Dynamic Programming、Upper and lower limits
    3. Data Structure 头脑风暴；常规处理方法头脑风暴，比如很多算法需要先对数据进行排序
    4. Bottlenecks / Unnecessary Work / Duplicated Work
  2. 算法的实现应该同时考虑到硬件资源和数据特性等多个方面，不同场景有不同的最优解

常见算法思想

技巧

  1. 在兼顾性能的同时，利用功能、边界和负面（错误输入）测试保证代码的完整性，例如：数值的整数次方 /

  2. 预先统计并分配相关资源，例如：替换空格 /

  3. 判断二进制中 1 的个数，为避免混淆逻辑右移和算术右移，使用额外变量左移与位运算进行计算

    1. 利用 bitset 需要注意位数的确定方式：sizeof(unint32_t) * 8

  4. 其他

穷举（暴力）

暴力算法意味着穷举所有可能，虽然效率低，但也不失为一种启发式算法。暴力算法常涉及递归，合理的使用递归可以简化代码，让代码更具可读性。以累加函数为例，递归代码比循环代码更加简短（但会消耗更多内存和时间）

std::size_t acc_sum(std::size_t n) {
	return n > 0 ? n + acc_sum( n - 1) : 0;
}

使用递归解题的前提是合理的对解题过程进行拆分，如果问题可以使用相同的子问题进行解决，就可以使用递归。穷举算法的时间复杂度一般与解的个数有关

leetcode 题目：77. 组合 / 无重复字符串的排列组合 /

贪心算法

贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的

时间调度问题常用贪心算法处理，但如何证明贪心算法一定能获得最佳解？

贪心算法可以获得一个解，但这个解不一定是最优的。贪心的核心是局部最优，所有此类操作有一定的规律形，例如从一侧到另一侧

leetcode 题目：135. candy & 信息丢失 & size 反转 / 435. 无重叠区间 / 605. 种花问题 & 跳格 / 452. 用最少数量的箭引爆气球 / 763. 划分字母区间 & 预先统计信息 / 665. 非递减数列 & 避免断崖式下跌 / 剪绳子 II /

分治法

可以结合主定理和递归树来思考分治法的优化方向，减少子任务的个数与规模可以降低算法的时间复杂度，如二分查找、矩阵计算等

分治算法（Divide and Conquer）的递归终止条件是 \(n=k\)，其中 \(k\) 是其他算法优于分治算法的分界线。分治算法的时间复杂度常由 \(T(n)=aT(\frac n b) + O(1)\) 给出。依主定理分析，当 \(log_b a > 0\) 时，\(T(n)=O(n^{log_b a})\)。尽可能减少子问题的个数，或者说多个子问题可以由其中一个子问题通过 \(O(1)\) 时间求解，即降低 \(a\) 的值可以降低递归算法的时间复杂度。典型的分治算法有二分查找（lower_bound，\(log(n)\)）、幂乘的递归求法(\(log(n)\))、二分归并算法(\(nlog(n)\))等

使用辗转相除思想求解最大公约数的 GCD 算法（Euclidean 算法）几乎每个算法书籍都会提及，这是分治法的典型应用；斐波那契数列有通项公式（\(F[n]=\frac{1}{\sqrt{5}}\left[\left(\frac{1-\sqrt{5}}{2}\right)^{n}-\left(\frac{\sqrt{5}+1}{2}\right)^{n}\right]\)），所以可以在 \(O(1)\) 时间复杂度内完成通项计算。利用分治法与公式（\(\left[\begin{array}{cc}F_{n+1} & F_{n} \\ F_{n} & F_{n-1}\end{array}\right]=\left[\begin{array}{ll}1 & 1 \\ 1 & 0\end{array}\right]^{n}\)），第 \(n\) 项也可以在 \(O(log(n))\) 时间复杂度内完成

leetcode 题目：

  1. 汉诺塔问题 / 二维数组中的查找 /

  2. 旋转数组中的最小值，特殊情况需要同时处理两侧。为简化二分对相邻数据的处理过程，可利用 min_element 直接处理短数组

  3. 其他

动态规划

动态规划与递归类似，都是将问题分解问小问题进行求解。动态规划在计算过程中会保存一些数据避免重复计算，所以动态规划相比于递归有时间上的优势

相关题目：

  1. 剪绳子 I /

回溯与分支界限

回溯法可以看成蛮力法的升级版，它从解决问题每一步的所有可能选项里系统地选择出一个可行的解决方案

用回溯法解决的问题的所有选项可以形象地用树状结构表示。在某一步有 n 个可能的选项，那么该步骤可以看成是树状结构中的一个节点，每个选项看成树中节点连接线，经过这些连接线到达该节点的 n 个子节点。树的叶节点对应着终结状态

相关题目：

  1. 矩阵中的路径，结合递归，注意移动方向

网络流

货郎（旅行商（TSP））问题至今没有找到多项式时间复杂度求解算法，但非精确的随机算法可以在有限时间内给出可用解；

#algs
Previous 算法学习
Next 数学拾遗