时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点就在于此。一般情况下，无法有效判断得到的解是否肯定正确。 32.拉斯维加斯算法

不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。 33.舍伍德算法

总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。

舍伍德算法 sherwood algorithm

舍伍德算法 一类概率算法的代称。此类算法总能给出所求问题的正确的解。...当解决某一问题的确定性算法的平均情形复杂性比最坏情形复杂性低得多时，通过引入随机性来试图减少甚至消除“好”、“坏”实体之间这种时间上的差别，以期望较小的运行时间。例 ...

五、算法设计与分析题

1．用动态规划策略求解最长公共子序列问题： （1）给出计算最优值的递归方程。

（2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出

其最长公共子序列，要求给出过程。

答： (1)

当i?0或j?0时?0?c[i,j]??c[i?1,j?1]?1当i,j?0且xi?yi时

?max(c[i,j?1],c[i?1,j])当i,j?0且xi?yi时?(2)

Ｙ Ａ Ｂ Ｃ Ｂ Ｘ 0 0 0 0 Ｂ 0 0 1 1 1 Ｃ 0 0 1 2 2 Ｄ 0 0 1 2 2 Ａ 0 1 1 2 2 最长公共子序列：｛ＢＣ｝

2．对下列各组函数f (n) 和g (n)，确定f (n) = O (g (n)) 或f (n) =Ω(g (n))或f(n) =

θ(g(n))，并简要说明理由。

(1) f(n)=2n； g(n)=n! (2) f(n)=n； g (n)=log n2 (3) f(n)=100； g(n)=log100 (4) f(n)=n3； g(n)= 3n (5) f(n)=3n； g(n)=2n 答：

(1) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。 (2) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。 (3) f(n) = θ(g(n)) 因为g(n)与f(n)同阶。 (4) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。 (5) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。

3．对下图所示的连通网络G，用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。

1 11 5 18 21 26 6 17 19 15 2 9 4 7 3 6 答：

TE={(3,4), (2,3),(1,5),（4,6）（4,5）}

贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。 基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。

时间复杂度为：O(eloge)

4. 请用分治策略设计递归的归并排序算法，并分析其时间复杂性（要求：分别给出divide、conquer、combine这三个阶段所花的时间，并在此基础上列出递归方程，最后用套用公式法求出其解的渐进阶）。 答 ： Template

void MergeSort (Type a[ ], int left, int right) { if (left

}

Divide 阶段的时间复杂性： O(1) Conquer阶段的时间复杂性： 2T(n) Combine阶段的时间复杂性： Θ(n)

θ(1)当n?1?T(n)?? ? 2T(n/2) ? θ(n) 当n ? 1

用套用公式法：a=2, b=2, nlog ba = n , f(n)=n, 因为f(n)与nlog ba 同阶， ∴T(n) =Θ(nlogn)

5、设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表: 每个选手必须与其他n-1名选手比赛各一次;每个选手一天至多只能赛一次; 循环赛要在最短时间内完成.

(1)（4分）循环赛最少需要进行( n-1 )天. (2)（6分）当n=23=8时,请画出循环赛日程表: