如何理解算法

从经济学的角度来看，人类的一切行为都可以视作经济问题，也就是成本问题。而算法的设计正是为了达成一个目的，即做一件事情尽可能付出最低的成本，从计算机的角度则为求一个问题的最优解。高效率的人正是贯彻这一思想，微观到解一道数学题，或者宏观到系统性的完成一项大工程。

什么是算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，所有可能的合法的输入都能产生预期的正确的结果。

重要的特性

有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义，不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径。
可行性：一个算法是能行的。即算法中描述的操作是执行有限次运算来实现的。
输入：一个算法有零个或多个输入。
输出：一个算法有一个或多个输出。

设计的要求

通常设计一个“好”的算法，应考虑达到以下目标。

正确性：算法应当满足具体问题的需求。
可读性：算法维护需要利于人的阅读与交流，可读性好有助于人对算法的理解，当然这个可读性好是相对概念，取决于面向的对象，绝大多数情况下不应为了可读性而牺牲效率，不然就本末倒置了。
健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生无法理解和随机的输出结果。
效率与低存储量需求：效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。

常用的思想

主流的八大算法思想为：穷举，递归，递推，分治，贪心，回溯，动态规划，模拟。

- 分而治之当然很好，但是并不是所有问题都可以，比如质因数分解问题。
- 递归也很好，一种调用自身的编程技巧，大大减少了代码量。
- 贪心以局部最优解求取全局最优解，追求的是高效率和近似解，可以理解为动态规划的一种特例。
- 动态规划的本质是定义状态和状态转移方程，实现则通过递推+Memory（剔除重复计算）的组合。
  - DP 状态
    - 符合「最优子结构」原则：DP 状态最优值由更小规模的 DP 状态最优值推出
    - 符合「无后效性」原则：状态的得到方式，不会影响后续其它 DP 状态取值
  - DP 转移方程
    - 分类讨论，细心枚举

递归与递推
以斐波那契数列为例

递归求解（从未知到已知）

int Fib(n) {
    return n < 2 ? 1 : fib(n-1) + f(n-2);
}

递推求解（从已知到未知）

int Fib(int n) {
    int fn   = 1;
    int fn_1 = 0;
    for(int i=0; i<n; i++) {
       int t = fn
       fn    = fn + fn_1;
       fn_1  = t;
    }
    return fn;
}

PS：动态规划的解法

static int DP_Fib(int n) {
    int[] arr = new int[n+1];
    arr[0] = 0;
    arr[1] = 1;
    for (int i = 2; i <=n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[n];
}

回溯代码框架

result = []
def backtrack(路径, 选择列表):
  if 满足结束条件:
    result.add(路径)
    return

  for 选择 in 选择列表:
    做选择
    backtrack(路径, 选择列表)
    撤销选择

动态规划代码框架

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
  for 状态2 in 状态2的所有取值：
    for ...
       dp[状态1][状态2][...] = 求最值（选择1，选择2，...）

解决什么问题

可计算问题：可计算问题才可设计算法。
计算密集问题（优化）：根据冯·诺依曼体系结构可知，计算机资源应对的两大核心问题为IO密集与计算密集。

可计算问题

假设有一个通用的模型，只要能被这个模型计算的问题，称为可计算问题，否则就是不可计算问题，而这个通用模型就是图灵机。

当今计算机算法领域的圣杯：P = NP问题（7大千禧年难题之一）。
P：可在多项式时间内解决。
NP：可在多项式时间内验证如素数验证。
猜想：一个万能算法可以把NP问题复杂度降到P类问题上来。
目前进度：有一类NP完全问题（NPC问题，常见的比如：蛋白质折叠，快递员问题，质因数分解）属于NP问题，一但其中一个问题能够降到P，则所有问题都能。

算法的定量分析

时间复杂度

复杂度 = 计算宽度 x 计算深度
计算宽度：一个集合中一个元素处理时所消耗的步数上界
计算深度：一个集合中所有元素分层（分级）处理的层数（级数）上界
比如快速排序复杂度 = 宽度(n) x 深度(log_mn)

常量级 O(1) 如：HashMap查询
亚线性 O(log_mn)
线性 O(n)
对数级 O(nlog_mn) 如：1 快速排序，2 动态规划行军路线 O(nlgn+L) n:节点数 L:线段数
指数级 O($m^{n}$) O($n^{m}$) 如：冒泡排序O($n^{2}$)
阶乘级 O(n!) 如：邮递员问题

空间复杂度

记为S(?)

通常空间和时间是联动的，但是相对来说，空间资源更经济，而且很多时候需要采取空间换时间的策略，所以这里暂时不做讨论。

工具

待补充… …

参考

Koupit Cialis

Loy Wong