|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
从算法的结构上看，算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单，本小节主要讨论递归算法的时间复杂度分析方法。
|
|
|
|
（1）展开法。将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直至得到一个求和表达式及其结果。
|
|
|
|
（2）代换法。这一名称来源于当归纳假设用较小值时，用所猜测的值代替函数的解。用代换法解递归式时需要两个步骤：猜测解的形式；用数学归纳法找出使解真正有效的常数。
|
|
|
|
（3）递归树法。递归树法弥补了代换法猜测困难的缺点，它适于提供"好"的猜测，然后用代换法证明。在递归树中，每一个节点都代表递归函数调用集合中每一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。当用递归式表示分治算法的时间复杂度时，递归树的方法尤其有用。
|
|
|
|
（4）主方法。也称为主定理，给出求解以下形式的递归式的快速方法，即
|
|
|
|
|
|
式中，a≥1和b>1是常数；f(n)是一个渐进的正函数。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
若矩阵中元素（或非零元素）的分布有一定的规律，则称之为特殊矩阵。常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。
|
|
|
|
|
|
|
|
|
|
上（下）三角矩阵：矩阵的上（下）三角（不包括对角线）中的元素均为常数或零。
|
|
|
|
对角矩阵：矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。
|
|
|
|
|
|
在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。存储稀疏矩阵的非零元素时必须同时存储其位置（行、列号），用三元组（i,j,aij）可唯一确定矩阵中的一个元素。因此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。
|
|
|
|
稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。
|
|
|
|
|
|
|
|
|
|
|
|
|
.png)
