矩阵乘法的Strassen算法 若A=(aij)和B=(bij)是n×n的方阵，则对i，j=1，2，3，…，n，定义乘积C=A•B中的元素cij为： 我们很容易得到一个执行时间为Θ(n3)的算法来计算矩阵乘法，因为矩阵乘法的的自然定义就需要进行这么多次的标量乘法。然而实际上，我们有方法在o(n3)时间内完成矩阵乘法：Strassen的著名n×n矩阵相乘的递归算法。后面它将被证明运行时间为Θ(nlg7)——渐近复杂性优于简单的矩阵乘法过程。 一个简单的分治算法 假定将A、B和C均分解为4个n/2×n/2的子矩阵： 因此可以将公式C=A•B改写为： ...

在分支策略中，我们递归地求解一个问题，在每层递归中应用入下三个步骤： 分解步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。 解决步骤递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解。 合并步骤将子问题的解组合成原问题的解。 当子问题足够大，需要递归求解时，我们称之为递归情况。当子问题变得足够小，不再需要递归时，我们说递归已经“触底”，进入了基本情况。 使用递归式可以很自然地刻画分治算法的运行时间。一个递归式就是一个等式或不等式，它通过更小的输入上的函数值来描述一个函数。例如用递归式描述归并排序过程的最坏情况...

当输入规模足够大，使得只有运行时间的增长量级有关时，我们要研究算法的渐进效率。 渐近记号 Θ记号 Θ记号渐近地给出一个函数的上界和下界。对一个给定的函数g(n)，用Θ(g(n))来表示以下函数的集合： 值得注意的是，我们通常会用这样一种方式活用等式：用“f(n) = Θ(g(n))”表达与"f(n) ∈ Θ(g(n))"相同的概念。 对于所有n≥n0，如果函数f(n)在一个常量因子内等于g(n)，我们称g(n)是f(n)的一个渐近紧确界。 Ο记号 当只有一个渐近上界时，使用Ο记号。对于给定的函数g(n)，用Ο(g(n))...

第1章 第1章内容是此书的导读章节，所以在此只对一些第一次出现的必要的概念和有助于理解此书的段落进行摘抄或总结。 算法：非形式地说，算法（algorithm）就是任何良定义的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。这样，算法就是把输入转换成输出的一个计算步骤的序列。 数据结构：数据结构是一种存储和组织数据的方式，旨在便于访问和修改。 虽然可以把本书当做一本有关算法的“菜谱”来使用，但是也许在某一天你会遇到一个问题，一时无法很快找到一个已有的算法来解决它。所以本书将教你一些算法设计与分析的技术，...