应用算法串讲1：计算复杂度优化与组合优化

从事算法工作以来，涉猎过不少算法。有些算法被淘汰，有些如日中天，有些则退守在某些特定的领域中顽强地生存，并不断给算法工作者提供思想启发。自己的一个方向是算法在产业界的应用，一个很强烈的感受是即便新的算法层出不穷，真正在实践上有生命力的并不在于其思想有多炫，而是其算法特质能够最好地适应具体场景的需求。

这么多算法，什么时候用什么算法，是需要梳理清晰的。然而算法思想过于复杂，想用一两篇文章讲得面面俱到几乎不可能。所以笔者希望用一个系列专题试图从应用的视角统一串讲一下不同算法， 尽量少讲公式，着重从思想角度关注不同算法之间的横向联系和适用条件 ，希望对大家应用算法落地有些帮助。

最优化的一些简化约定

如果说非要找 一条主线串起来各种不同算法 ，笔者想来想去还是要靠 最优化 思想。最优化是一种非常直观的思想，一般来说是指：在有限的约束条件的下控制一些自变量使得目标（因变量）达到最大值（或最小值）的过程。所以它有以下 3个核心概念 ：

目标（因变量）： F(x)

自变量（控制条件）：x

约束：g(x) = 0

目标优化函数很大程度决定了算法种类。一般 “决策” 相关的问题的优化目标是价值函数， “预测” 相关的问题优化目标是预测误差。

函数作为自变量则构成了一个 套娃：目标函数F(f)是自变量函数f(x)的函数，这个自变量函数f(x)本身也有自己的自变量x 。这种情况还比较常见，绝大部分机器学习算法都是为了寻找一个预测函数f(x)，该函数的预测误差L(f)要尽量小。

程序本身可以视作一种特殊的函数，接下来要介绍的计算复杂度优化算法就一个典型例子。

另外，约束条件是对自变量的约束，可以是关于自变量的一组（不）等式方程。约束不是最优化问题的必须要有的，但十分常见，而且 加了约束的问题可能会更难 。

计算复杂度优化算法

计算复杂度优化算法是一类非常重要的算法，用之前约定的最优化形式描述如下：

最小化目标：时间复杂度T(f)与空间复杂度S(f)

自变量：一段程序f

满足条件（约束）：程序f能够实现某个特定的功能（可套娃）

对时间复杂度和空间复杂度的追求是贯穿在整个应用开发过程的。即便是机器学习相关算法，无论是训练还是预测，都需要持续关注时间空间相关的优化以及它们之间的权衡。

约束：组合最优化算法套娃

这里首先要注意的是 约束本身也可以是一个最优化问题，又构成了一个套娃 ，套娃玩出了花。

具体的最优化问题可以是：

1. 将长度为n的整数数组划分为m个片段（约束），最小化每个片段和的最大值（目标）——LeetCode1011。
2. 在长度为n的整数数组中，找出一个的和大于等于s的连续子数组（约束），最小化子数组的长度（目标）——LeetCode209。
3. 在长度为n的整数数组中，找出一个递增子序列（约束），最大化子序列的长度（目标）——LeetCode300。

里层套娃的最优化问题往往是一个带约束的组合优化问题，以LeetCode1011为例其形式化表述如下：

最小化目标（程序出参）：所有划分片段的子数组和的最大值。

自变量（程序入参）：长度为n的整数数组，整数m。

约束（程序必需满足逻辑）：将整数数组划分为m个子片段。

这类 组合优化问题难以通过梯度下降法之类的方法自动化处理，往往需要在可行约束空间中遍历可行解才能找到最优值 。所以 关键的是利用题目的特点降低遍历的时间复杂度 。处理它们的方法包括 二分查找、快慢指针、贪心与动态规划 等，分别适合处理最优化问题存在全局单调（有序）性、可行约束空间可排除、子问题之间的约束存在递推关系等情况，本质都是 降低遍历可行约束空间的计算量 。

组合优化不仅仅是存在于面试题中，在产业实践中也屡屡能看到他们的身影。而且目前的一个趋势是比较多地与机器学习、强化学习等方法结合。

当然，产业应用中的组合优化可能没有前面例子中存在多种特定简化条件那么理想。真实的情况可能极其复杂，如外卖订单聚和与分配等等。 实践中的处理方式可能会放弃全局最优的探索，而是争取一些好的局部最优结果，降低可行约束的探索空间。 如在序列化标注过程中可以用全局最优的维特比算法，但在机器翻译的推断过程中的可行空间十分巨大，便采用Beam search这样近似局部最优的算法以降低探索空间。

自变量：程序

附：系列框架图