01 绪论

  • 数据结构: 以”数据“这一信息的表示形式为研究对象,旨在建立支持高效算法的数据信息处理策略、技巧与方法。

1.1 计算机与算法

计算机科学的核心在于研究计算方法与过程的规律,而不仅仅是作为计算工具的计算机本身。因此,Dijkstra及其追随者更倾向于将这一门学科称为计算科学(computing sciense)

算法

  • 基于特定的计算机模型(计算机),旨在解决某一信息处理问题而设计的一个指令序列。

算法需要包括的要素:

  • 输入与输出

  • 基本操作、确定性和可行性

    • 算法应描述为由若干语义明确的基本操作组成的指令序列,且每一基本操作在对应的计算模型中均可兑现。

    • 从现在程序设计语言的角度,一个算法满足确定性与可行性,当且仅当它可以通过程序设计语言精确的描述。

  • 有穷性与正确性

    • 但程序不等于算法,如Hailstone程序是否是有限的,目前还没有定论

  • 退化与鲁棒性

    • 退化(degeneracy)即各种极端的输入。鲁棒性就是要求尽肯能的能够应对这些输入。

1.4 递归

为保证有穷性,递归算法都必须设置递归基(base case of recursion),且确保总能执行到。

分类

  • 线性递归:每一层的实例对自己调用一次。在每一层上都只有一个递归实例。

    • 线性递归一般对应减而治之(decrease-and-conquer)的算法策略。每次将问题规模缩减一个常数。

    • 线性递归中只会出现一个递归基

  • 二分递归:每一层的实例对自己调用两次。

    • 二分递归中会频繁出现递归基。会有超过半数的递归实例都是递归基。

  • 多分支递归:每一层的实例对自己调用多次。

下面分别是线性递归和二分递归来实现数组求和

// 线性递归
int sum(int A[], int n)
{
if (1 > n)
return 0;
else
return sum(A, n-1) + A[n-1]; // 注意着不是尾递归,最后一步不是递归调用,而是加法
}
// 二分递归,入口调用sum(A, 0, n-1);
int sum(int A[], int lo, int hi)
{
if(lo == hi) {
return A[lo];
} else {
int mi = (lo + hi) >> 1;
return sum(A, lo, mi) + sum(A, mi + 1, hi);
}
}

优化策略

  • 不用尾递归(注意上面线性递归的例子并不是尾递归)。理论上尾递归都可以转化为等效的迭代算法。

  • 消除重复的递归实例(借助一定的辅助空间,及时记录子问题的答案,避免重复),分为两种

    • 自顶向下,遇到出现过的子问题,则直接用之前的记录(称为制表(tabulation)或记忆(memoization))

    • 自底向上,从递归基出发,向上推得各子问题的解。(即动态规划)