算法设计与分析

1、 什么是算法？算法有哪些基本特征？请指出算法同程序的相同点与不同点。
（课件之“绪论”，教材之“绪论”， page:1 ）
1 ）算法： 解决问题的方法或过程。
2 ）基本特征：
输入：有零个或多个外部量作为算法的输入；
输出：算法产生至少一个量作为输出；
确定性：组成算法的每条指令是清晰的、无歧义的；
有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。
3 ）算法同程序的相同点与不同点：程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的有限性。
2、 请描述算法设计的一般过程。（课件之“绪论”）
1） 提出问题
2） 确定数学模型
3） 明确目的、条件与约束关系
4） 设计求解步骤
5） 结果评估与分析
3、 什么是算法复杂性？它主要有哪两个方面构成？（课件之“绪论”）
算法复杂性：算法运行时所需要的计算机资源的量；主要由时间复杂性和空间复杂性构成。
这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。
4、 时间复杂性分析主要分哪三种情况，哪种情况的可操作性最好，最具有实际价值？（课件之“绪论”）
时间复杂性分析主要分最好情况、平均情况、最坏情况；
可操作性最好，最具有实际价值的是最坏情况下的时间复杂性。
5、 熟练掌握算法复杂性分析中符号 “O” 的运算规则。 （教材之“绪论”， page:15 ）
设f(N)和g(N)是定义在正数集上的正函数。
O的定义：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。
1） O(f)+O(g)=O(max(f,g))
2） O(f)+O(g)=O(f+g)
3） O(f)O(g)=O(fg)
4） 如果 g(N)=O(f(N)) ，则 O(f)+O(g)=O(f)
5） O(Cf(N))=O(f(N)) ，其中 C 是一个正的常数
6） f=O(f)
时间复杂性按数量级递增排列：常数 O(1) 、对数阶 O(logn) 、线性阶 O(n) 、线性对数阶 O(nlogn) 、平方阶 O(n^2) 、立方阶 O(n^3) 、…、 k 次方阶 O(n^k) 、指数阶 O(2^n) 。
例子： 如果算法 A 由三个步骤组成，其中第一步的时间复杂性为 O(n^2) ，第二步的时间复杂性为 O(nlogn) ，第三步的时间复杂性为 O(n) ，请问算法 A 的时间复杂性是多少？（答案： O(n^2) ）
6、 请问二分搜索算法、快速排序算法、线性时间选择算法和最近点对问题的时间复杂性各为多少？
（教材之“递归与分治”， page:27,37,39,43 ）
1) 二分搜索： O(logn)
2) 快速排序： O(n^2) 最坏情况运行时间是O(n^2)，但期望时间是O(nlogn)。
3) 线性时间选择： O(n)
4) 最近点对问题： O(nlogn)
7、 分治算法和动态规划算法都是通过对问题进行分解，通过对子问题的求解然后进行解重构，从而实现对原问题的求解。请指出这两种算法在对问题进行分解时各自所遵循的原则。（课件之“递归与分治”，课件之“动态规划”）
分治算法：
将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题互相独立并且与原问题相同。通过递归地求解这些子问题，然后再将各个子问题的解合并，就可以实现对原问题的求解。
动态规划算法：
动态规划算法分解得到的子问题往往不是互相独立的,不同的子问题的个数只是多项式量级.用一个表来记录所有已解决的子问题的答案,不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中,而在需要时从表中找出已求得的答案,这样就可以避免大量的重复计算,从而得到多项式的时间算法.
其基本思想与分治算法的思想类似 —— 分而治之
与分治法的不同之处：分解后的子问题往往不互相独立；采用记录表的方法来保存所有已解决问题的答案。
8、 动态规划算法的本质是什么，请简要阐述。（课件之“动态规划”）
1) 动态规划算法的本质是分治思想和解决冗余，它将原问题进行分解，通过对子问题的求解然后进行重构，从而实现对原问题的求解。
2) 动态规划算法的基本思想：如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。
9、 如果一个问题可以利用动态规划算法求解，那么该问题应满足什么条件？（教材之“动态规划”， page:67 ）
应满足两个条件：最优子结构性质和子问题重叠性质
10、动态规划算法的基本思想是什么？请简述动态规划算法主要设计步骤。（教材之“动态规划”， page:61 ）
动态规划算法的基本思想：将原问题进行分解,通过对子问题的求解然后进行解重构,从而实现对原问题的求解.动态规划算法分解得到的子问题往往不是互相独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。
动态规划算法主要设计步骤：
1） 找出最优解的性质，并刻画其结构特征；
2） 递归地定义最优值；
3） 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
4） 根据计算最优值时得到的信息，构造一个最优解。
11、什么是备忘录方法？它同动态规划法相比主要不同点是什么？请指出动态规划法和备忘录方法各自的适用范围。（课件之“动态规划”）
备忘录方法是动态规划算法的变形。采用表格保存已经解决的子问题答案，下次需要时查看即可。
不同之处：
动态规划算法：自底向上递归求解
备忘录方法：自顶向下递归求解
适用范围：
l 当一个问题的所有子问题都至少要解一次时，建议使用动态规划算法
l 当子问题空间中的部分子问题不需要求解时，建议使用备忘录方法
12、贪心算法的设计思想是什么，有什么特点？如果一个问题用贪心算法可以获得全局最优解，那么该问题的求解应满足哪些条件？（课件之“贪心算法”，教材之“贪心策略” ,page110 ）
贪心算法的设计思想：通过一系列的选择得到问题的解；它所做出的每一个选择都是当前状态下局部最好选择，即贪心选择。
特点：
1 ）设计思想: 总是做出在当前看来最好的选择,不是从整体考虑 —— 得到的解可能不是全局最优
2 ）特点: 简单，直接，易理解，效率高
3 ）满足的条件：贪心选择性质和最优子结构性质
13、请简要描述回溯法的实现过程。用回溯法求解 0/1 背包问题、 TSP 问题、 N 皇后问题和连续邮资问题时，其各自的解空间树各是什么形式？ ( 课件之“回溯法”，教材之“回溯法” page147 ）
1 ）实现过程:
a ）在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。 当搜索到解空间树的任一结点时，先判断该结点是否包含问题的解。如果确定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
b ）求解问题性质.
回溯法求问题的所有解时,要回溯到根,且根节点的所有子树都被搜索遍才结束;
回溯法求问题的一个解时,只要搜索到问题的一个解即可.
2 ） 0/1 背包问题解空间树：子集树
TSP 问题解空间树：排列树
N 皇后问题解空间树：完全 n 叉树
连续邮资问题解空间树：树（该解空间树中各结点的度随 x 的不同取值而变化）
14 、 影响回溯法效率的主要因素有哪些？如何有效地估算回溯法在求解具体实例时产生的中间节点数量？
( 课件之“回溯法”，教材之“回溯法” page187 ， 188 ）
1） 影响回溯法效率的主要因素
a) 产生 x[k] 的时间
b) 满足显约束的 x[k] 值的个数
c) 计算约束函数 constrain 的时间
d) 计算上界函数 bound 的时间
e) 满足约束函数和上界函数约束的所有 x[k] 的个数
2 ）用概率方法估计将产生的中间节点数量。
主要思想：在解空间树上产生一条随机路径，然后沿该路径估算解空间中满足约束条件的接点树m 。直到延伸到叶节点或所有子节点都不满足约束条件为止
15 、 请简述分支限界法的算法思想以及两种主要的实现方法。
( 课件之“分支限界法”，教材之“分支限界法” page195 ， 196 ）
1）分支限界法的算法思想：以广度优先或以最小耗费优先的方式搜索解空间树，力求找出解空间树中满足约束条件的可行解或最优解。
2） 两种主要的实现方法：
a) 队列式 FIFO 分支限界法
将活结点表组织成一个队列，并按队列的先进先出 FIFO 原则选取下一个结点作为当前扩展结点。
b) 优先队列式分支限界法
将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级，选取剩余队列中优先级最高的下一个结点作为当前扩展结点。
16 、 请指出回溯法与分支限界法的相同点与不同点。 ( 课件之“分支限界法”）
1）相同点：
l 两者在进行问题求解前，都需要完成解空间的定义和组织 。
l 都是通过在解空间搜索来寻找问题的解 。
2）不同点：
a) 搜索方式
l 回溯法： 深度优先
l 分支限界法： 广度优先
b) 搜索策略
l 回溯法：根据剪枝函数，选择下一个扩展接点并按深度优先方式进行搜索。
l 分支限界法：在扩展结点处，先产生其所有的子结点（分支），然后根据限界函数，确定哪些子结点将导致不可行解或非最优解，将这些子结点剔除，用剩下的子结点构造当前的活结点表，然后从该表中取一个结点作为当前扩展结点，并重复上述过程。
17 、 概率算法主要有哪些类型？它们各自的主要特点是什么？如何有效提高概率算法获得正确解的概率或提高算法的求解精度？ ( 课件之“概率算法”，教材之“概率算法” page241 ）
1）概率算法主要类型：数值概率算法；蒙特卡罗算法；拉斯维加斯算法；舍伍德算法。
2）主要特点：
a) 数值概率算法 ：
常用于数值问题的求解，得到的往往是近似解
解的精度随计算时间的增加而提高
在许多情况下，计算出问题的精确解是不可能或没必要
b) 蒙特卡罗算法：
用于求解问题的准确解
在有些情况下，近似解没有意义，比如“ 0/1” 判定问题
可以求得问题的一个解，但该解未必正确
求得正确解的概率依赖于算法的计算时间
蒙特卡罗算法的主要缺点就在于无法有效判定所得到的解是否肯定正确。
c) 拉斯维加斯算法：
不会得到不正确的解,但有时找不到问题的解
找到正确解的概率随算法计算时间的增加而提高
用同一拉斯维加斯算法反复对问题实例求解足够多次，可使求解失败的概率任意小。
d) 舍伍德算法：
总能求解得到问题的一个解，而且所求得得解总是正确的。
当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可在这个确定算法中引入随机性，将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的差别。
舍伍德算法的精髓
不是避免算法的最坏情况，而是设法消除这种最坏情形行为与特定实例之间的关联性 。
3 ）精度随计算时间的增加而不断提高。
18、 对于NP完全问题,我们一般采取的求解策略主要有哪些?(课件之”近似算法”,教材之”近似算法” page326)
只对问题特殊实例求解;
用动态规划法或分支限界法求解;
用概率算法求解;
只求近似解;
用启发式方法求解.
======================
算法分析
一算法引论
什么是算法,它的特点 算法与程序的联系与区别
算法设计的一般过程
算法复杂性的基本概念,大O算法
二分治法
分治法的基本思想,递归的概念
二分搜索技术,快速排序,线性时间选择
特征:
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
利用该问题分解出的子问题的解可以合并为该问题的解；(不具备:贪心法或动态规划法)
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 (不具备:动态规划法)
分治法在每一层递归上都有三个步骤：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
合并：将各个子问题的解合并为原问题的解。
二分搜索技术
问题描述：给定已经排好序的n个元素a[0:n-1]，现在要从这n个元素中找出一个特定的元素x。
解决方案
方案1：逐个比较——算法复杂度为O(n)
方案2：利用元素间的次序关系，采用分治策略，可在最坏情况下用O(logn)时间完成任务。
Public static int binarySearch(int[]a,int x,int n)
{
//找到x时返回其在数组中的位置，否则返回-1；
int left=0;int right=n-1;
while(lefta[middle]) left=middle+1;
else right=middle-1;
}
return -1; //没找到
}
快速排序
基本思想
对于输入的子数组a[p:r]，按分治策略的基本步骤进行求解；
分解：以a[q]为基准元素将a[p:r]划分成三段：a[p:q-1]、a[q]和a[q+1:r]，使得
a[p:q-1]中任何元素≤a[q]
a[q+1:r]中任何元素≥a[q]
递归求解：通过递归调用快速排序算法，分别对a[p:q-1] 和a[q+1:r]进行排序；
合并：将排序好的a[p:q-1]和a[q+1:r]， 按照以下方式合并
a[p:q-1] =[a[p:q-1],a[q],a[q+1:r]]
Private static void qSort(int p, int r)
{
if(px的元素交换到右边区域
while(true)
{
while(a[++i].compareTo(x)x的a<i>
while(a[–j].compareTo(x)>0); // –i，直到找到=j) break;
MyMath.swap(a,i,j); //交换a<i>、a[j]的位置
}
a[p]=a[j];
a[j]=x;
return j;
}
快速排序算法的复杂性分析
运行时间与划分是否对称有关
最坏情况：对于一个包含n个元素的数组，被划分成两个区域，其中一个包含n-1个元素，而另一个中只有一个元素。
最好情况：每次划分都产生两个大小为n/2的区域。
快速排序算法在平均情况下的时间复杂性是O(nlogn)
通常基于比较的排序算法的算法复杂度是O(n2)
线性时间选择
元素选择问题
给定线性序集中的n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。
当k=1时——找最小元素；
当k=n时——找最大元素；
当k=(n+1)/2——找中位数
算法设计思想
与快速排序算法的设计思想基本相同，即对输入数组进行递归划分，但操作上只对划分出的两个子数组中的一个进行进一步的递归处理；
Private static Comparable randomizedSelect(int p, int r, int k)
{
if(p==r) return a[p];
int i=randomizedpartition(p,r);
int j =i-p+1;
if(k
三 动态规划
基本思想
设计步骤
可用算法求解的问题,所具有的一般特性(最优子结构性质,子问题重叠性质)
备忘录方法(同算法比较)
矩阵连乘,图像压缩,0-1背包
该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
矩阵连乘
1,分析最优解的结构
将矩阵连乘积AiAi+1…Aj记作A[i:j]
把问题转化成考察A[1:n]的最优计算次序问题
关键特征
A[1:n]的最优计算次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。
——问题的最优解包含了其子问题的最优解，这种性质称为最优子结构性质。
2,建立递归关系
设计算A[i:j],1≤i≤j ≤n，所需的最少数乘次数为m<i>[j]
——则原问题的最优解为m[1][n]
考察两种情况
i=j;
i
图像压缩
0-1背包
四 贪心
基本思想和特点
可用算法具有的性质:最优子结构性质和贪心选择性质
活动安排,最优装载
贪心算法的基本思路如下：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
活动安排
最优装载
五 回溯
基本思想
问题解空间的定义和组织
剪枝函数的设计
0-1背包,TSP,图的m着色,骑士巡游
回溯法的效率分析,,原理,估算中间结点
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：
一、定义一个解空间，它包含问题的解。
二、利用适于搜索的方法组织解空间。
三、利用深度优先法搜索解空间。
四、利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
六 分支界限
基本思想
同回溯法的异同点
两种基本的实现方法
装载问题
七 概率算法
特点
4种主要类型的概率算法及其各自的特点
2-3,2-4,2-9,2-15,3-15,4-6
2-3参考答案：二分搜索算法的基本流程不变，增加两个变量用来保存当前找到的i,j的值，每次基于中间元素（假定为Ai）进行一次集合划分后，将当前集合分成两个子集合，令i等于前一个集合的最后一个元素的位置，j等于后一个集合的最前面一个元素的位置，如果当前的中间元素等于所要寻找的元素x，则i=j=该中间元素的位置。以上调整对二分搜索算法的时间复杂性并不造成影响。
2-4 参考答案：如果n远大于m，则将整数u划分成n/m段，每段分别与v按大整数乘法的算法进行运算（整数长度为m），然后分别进行移位（即乘以2的不同阶幂，根据该段在u中的划分位置）在相加即可，由于总共进行了n/m次m位整数的乘法，每个m位整数的乘法算法复杂性为O(mlog3)，所以总的算法复杂性为
O(n/m* mlog3)= O(nmlog3-1)= O(nmlog3-log2)= O(nmlog3/2)
2-9参考答案：
根据主元素的定义，如果T中包含一个主元素（假定为x），则T中必定有n/2个元素要不小于或不大于x，则如果我们将T中的元素按从小到大排列的话，第n/2个元素必定为x。由此，我们可以将原题进行转换，分以下两步进行：
l 首先，用线性选择算法找到T中第n/2小的元素x，该步骤的算法复杂性即为线性时间选择算法的算法复杂性，为O（n）。
l 扫描整个数组T[0:n-1]一遍，统计T中等于x的元素数，如果总和>n/2，则x为主元素；否则，表示T中没有主元素；该步骤为一线性扫描过程，比较操作计算复杂性为O（1），最多需要进行n次比较，所以整个步骤的算法复杂性为O（n）；
总的算法复杂性为O(n)+O(n)=O(n)（算法实现过程简单，略。）
2-15参考答案：首先对数组相邻的两个进行比较，将大的放在后面，小的放在前面，然后在两个数中小的所有数选出最小，同时也在两个数中大的所有数选出最大的。这样我们可以得出总的比较次数：(int)(n/2)+2*((int)(n/2)-1).
这里由于考虑n的取值，比较次数要少于等于n＋cell（logn）－2，当n为2的幂方时，取等号。（cell这里表示取上界）
3-15 参考答案
算法提示：本题的求解思路同图象压缩问题类似，假定总共在m个位置进行了租船活动，从最后一次租船位置向前进行分析。
先假定最后一次租船位置（即出租站编号）为k，则k可能的位置为i,2,…,j-1
则最优租船方案所对应的最少租金为
如果m<i>[j]是最优的，则m<i>[k]也是最优的，原问题的最优解包含其子问题的最优解，说明该题具有最优子结构性质。（反证法，过程略）
递归方程为：
在计算最优值的过程中，利用数组保存中间信息（即k的值），然后利用保存在数组中的中间信息完成对最优解的重构。
4-6：这道题可以用贪心算法求解：按li的长度作非递减顺序存储程序，此时平均读取时间最短。
其正确性证明如下：
1． 该问题符合贪心性质，设程序已以其长度从短到长排序，（x1,x2,…xn）是问题的最优解。又设k 是排序好后的序列的第一个程序的编号。1
（1） 当k = 1 时，该序列是一个满足贪心选择性质的最优解。
（2） 当 k 1 时，将xk与x1交换，设原解法总读取时间为T，此时总的读取时间为T0 T，因为这样使原来序列中在xk前面的程序的读取时间减少，而且x1和xk的读取时间也比原序列中少。所以改变后的序列是程序最优存储问题的可行解。
另一方面 T0 = T，知改变后的序列是满足贪心选择性质的最优解。
所以程序最优存储问题具有贪心选择性质。
2． 该问题符合最优子结构性质，即原问题的最优解包括了子问题的最优解。
反证法：假设存在一个原问题的最优解，而这个原问题的最优解不包括了子问题的最优解，则一定存在一个比原问题最优解更优的解法，将这个解法替代原问题的相应部分。这样可以得到一个更优的解。这与这个原问题的解释最优解矛盾。
算法主要的时间是花在排序上，所以算法复杂度是O(NlogN)