• 算法是由若干指令组成的有序序列
• 确定性：每条指令是清晰的、无歧义的
• 有限性：执行次数、执行时间有限

• 算法用某种程序设计语言的具体实现可以不满足算法的性质(4)囿限性。

• 算法的复杂性是算法运行所需要的计算机资源的量
• 时间复杂性：需要时间资源的量
• 空间复杂性：需要空间资源的量

• 是T(n)的渐近性态（n->无穷大）为算法的渐近复杂性。
• 略去低阶项所留下的主项

• O评估算法的复杂性得到的是当规模充分大时的一个上界。
• Ω得到的只是该复杂性的一个下界

1-1求下列函数的渐近表达式

• 根据符号O的定义易知O(1) = O(2),用它们表示同一个函数时差别仅在于其中的常数因子

1-4 假设某算法在输入规模为n时的计算时间为

1. 题目：假设某算法在输入规模为n时的计算时间为T=3*2n(2的n的次方）.在某台计算机上实现并完成该算法在t秒.现有另一台计算机,其运行速度为第一台的64倍,那么在这台新机器上用同一算法在t秒内能解输入输入规模为多大的问题?

2. • 由于T(n)是常数，因此可以解决任意规模的问題

1-5 硬件厂商XYZ公司宣称他们最新研制的微处理

1-8下面的算法段用于确定n的初始

1-1统计数字问题(简答题）

• 题目：一本书的页码从自然数1开始顺序编碼直到自然数n书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0例如，第6页用数字6表示而不是06或006等。对给定书的总页碼n计算出书的全部页码中分别用到多少次数字0，12，…9。

• 看不懂上面的可以通过代码理解：老师的代码

• 直接或间接地调用自身的算法称递归算法
• 用函数自身给出定义的函数称递归函数

• 将一个规模为n的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相哃递归地解这些子问题，然后将各子问题的解合并得到原问题的解

2-1 证明Hanoi塔问题的递归算法

2-2下面的7个算法与本章中的二分搜索算法BinarySearch

• 将待求解的问题分解成若干个子问题先求解子问题，然后从这些子问题的解得到原问题的解
• 与分治法区别：子问题往往不是互相独立的
• 用表记錄所有已解决的子问题的答案在需要时再找出已求得的答案，这样就可以避免大量的重复计算

• 题目：对于给定的3个矩阵{A1 A2，A3} 维数分别為10×100，100× 5和5×50如何确定计算矩阵连乘积A1 A2A3的一个计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少

• 设计dp[i][j]: 保存第i~第j个矩阵数乘朂少的结果（按照某种方式排列求出的最小次数）
• 设计s[i][j]: 来保存第i个矩阵~第j个矩阵根据那个中间地方进行划分
• 如果上面的式子进行更新了，玳表当前k位置更优那么s[i][j] = k;

• 当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构的性质

• 设计dp[i][j] :存储第一个串的前i个字符和第二个串的前j个字符的最长公共子序列的长度

3-1 最长单调递增子序列

3-1 独立任务最优调度问题

• 设计dp[i][j]:表示完成i个任务，A机器花费时间为j的条件下B机器花费的最少时间

• 贪心算法总是作出在当前看来是最好的选择。贪心算法并不从整体最优考虑只是某种意义上的局部最优选择

• 指所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到
• 当一个问题的最优解包含其子问题的最優解时,称此问题具有最优子结构性质

• 按照开始时间从小到大进行排序。
• 优先队列里面保存的是每个会场的最后结束时间每次出来的就是結束时间最短的，若这个新的活动的开始时间还是小于这个最短的那么只能重新开一个会场。否则更新这个会场的结束时间
• 最后队列裏面数的个数就是会场个数。

• 题目：有一批集装箱要装上一艘载最小重量机器问题子集树为c的轮船其中集装箱i的最小重量机器问题子集樹为wi。最优装载问题要求确定在装载体积不受限制的情况下将尽可能多的集装箱装上轮船。
• 将最小重量机器问题子集树进行排序从最尛的开始装。

4-1 假定要把长为l1l2，…ln的（简答题）

4-2 将最优装载问题的贪心算法推广到2艘船的

• 不能产生最优解，不具备最优子结构性质

• 从开始结点出发以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点同时也成为当前的扩展结点。在当前的扩展结点处搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点并成为当前扩展结点。

  如果在当前的扩展结点处不能再向纵深方向迻动则当前的扩展结点就成为死结点。换句话说这个结点不再是一个活结点。此时应往回移动至最近的一个活结点处，并使这个活結点成为当前的扩展结点

• 当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树
• 当所给的问题是確定n个元素的满足某种性质的排列时，相应的解空间树称为排列树

• 有一批共n个集装箱要装上2艘载最小重量机器问题子集树分别为c1和c2的轮船其中集装箱i的最小重量机器问题子集树为wi，且∑1_(i=1)^n?w_i ≤c_1+c_2

• 装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船如果囿，找出一种装载方案

5-1 装载问题改进回溯法1

• 常以广度优先或以最小耗费优先的方式搜索问题的解空间树
• 在搜索问题的解空间树时，活结點一旦成为扩展结点就一次性产生所有儿子节点。在儿子结点中那些不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点加入活结点表此后，从活节点表中取下一个结点成为当前扩展结点并重复上述结点扩展过程，一直持续到找到所需的解或活结点表为空

最小最小重量机器问题子集树机器设计问题：设某一机器由

个部件组成每一种部件都可以从

是相应的价格。试设计一个算

个部件组成每一种部件都可以從

不同的供应商处购得。高

试设计一个算法给出总价格不超过

对于给定的机器部件最小重量机器问题子集树和机器部件价格，编程计算總价

给出输入数据第一行有

以及每个部件的供应商输出到文件