算法导论-2.随机算法习题选
算法导论-2.随机算法习题选<div id="cnblogs_post_body">算法导论里的习题，有很多都是经典，不少题目都做不出来，到网络上找答案，再自己慢慢理解，这样的过程使我受益。我精选了一部分习题，写出思路作为存档以供查阅。从这篇博文开始，我尝试使用MathJax来显示公式，而不是之前若干篇博文中使用图片，如果你的浏览有什么问题，请告诉我。
前两题是算法入门一节挑的，太少就没有单独做一篇。
练习2.3-7 给出运行时间为 $\Theta(nlgn)$ 的算法，使之能在给定一个由 $n$ 个整数构成的集合 $S$ 和另一个整数 $x$ 时，判断 $S$ 中是否有两个和为 $x$ 的元素。
思路：首先用合并排序将数组 $S$ 排序，所需要的运行时间为 $\Theta(nlgn)$ 。再用两个哨兵一头一尾向中部&ldquo;巡逻&rdquo;，如果两个哨兵的和恰巧为 $x$ ，则找到解，如果哨兵之和大于 $x$ 则将右侧哨兵左移一格，若哨兵之和小于 $x$ 则将左侧哨兵右移一格，直到两个哨兵相遇，这个过程所需要的运行时间显然是 $\Theta(n)$ ,整个算法的运行时间为 $\Theta(nlgn)+\Theta(n)=\Theta(nlgn)$ 。
思考题2-4.d 给出运行时间为 $\Theta(nlgn)$ 的算法，确定 $n$ 个元素的排列 $S$ 中逆序对的数目。（提示：修改合并排序。）
思路：将 $S$ 的某个子集 $$ 分成两个子集 $$ 和 $$ 。$$ 中逆序对的数目等于两个子集各自内部的逆序对数目和子集间逆序对的数目&mdash;&mdash;前者可以递归地求解，直到子集中只有一个元素，逆序对数目为 $0$ ，后者在两个子集已经排过序的情况下也可以在线性运行时间下求得（该过程的伪代码如下）。
<div class="cnblogs_code">INVERSE_NUM(s, p, q, r)/*s and s are sorted*/while i=q to p, j=r to q+1 if s>=s result+=j-q i-- else j--
页:
[1]