3.3　习题

3.1　请采用数学归纳法证明插入排序(算法5)的正确性。
3.2　（冒泡排序）　冒泡排序(算法6)对数组A［1..n］中的元素进行排序。算法6：BUBBLE-SORT(A［1..n］)
1　for i∶=n downto 2 do
2　for j∶=1 to i-1 do
3　if A［j］>A［j+1］ then
4　SWAP(A［j］, A［j+1］);1） 请证明冒泡排序的正确性。
2） 请分析冒泡排序的最坏情况、平均情况时间复杂度。(注：我们以元素的比较为关键操作，数组元素的交换不计入关键操作。)
3） 我们可以改进冒泡排序来避免在数组尾部进行的不必要的比较操作，具体做法是记录每次循环中最后发生元素交换的位置。假设最后一次元素交换发生在A［k］和A［k+1］之间，则记录下这一位置。未来的数组遍历就不用再扫描下标k之后的元素。请说明这样的做法是否会影响算法的最坏情况和平均情况时间复杂度。
3.3　假设有一堆数量为n的大小互不相同的煎饼，现在需要对这些煎饼排序，使得小的煎饼放在大的煎饼上面。仅可以使用的操作是用一个锅铲插入到最上面的k（1≤k≤n）个煎饼下面，然后将它们一起翻转过去。图3.2给出一个翻转最上面两块煎饼的例子。请针对该问题设计算法，证明算法的正确性，并分析算法的时间复杂度。
图3.2　翻转最上面的两块煎饼
3.4　给定一个数列〈a1,a2,…,an〉，PREVIOUS-LARGER算法对数列中的每个元素ai(1≤i≤n)，找到序列中位于ai左边且值比ai大的元素。如果存在多个这样的元素，须返回最右边元素的下标；如果不存在这样的元素，则返回特殊值0。1　Algorithm:PREVIOUS-LARGER(A［1..n］)
2　for i∶=1 to n do
3　j∶=i－1;
4　while j>0 and A［j］ do
5　j∶=j－1;
6　p［i］∶=j;7　return p［1..n］;导致该算法效率不高的一个原因是语句“j∶=j－1”，它使得我们的寻找每次只能向前推进一个元素。可以考虑利用前面已经得到的数组p［1..n］中的值来提高算法的效率。请利用这个提示设计一个复杂度为Θ(n)的算法，证明算法的正确性，并分析算法的时间复杂度。
3.5　假设现在需要颠倒句子中的所有单词的顺序，例如“My name is Chris”，颠倒句子中的所有单词得到“Chris is name My”。请设计一个算法解决该问题，并分析算法的时间和空间复杂度。
3.6　（微博名人问题）　给定n个人。我们称一个人为“微博名人”，即他被其他所有人微博关注，但是自己不关注任何人。为了从给定的n个人中找出名人，唯一可以进行的操作是：针对两个人A和B，询问“A 是否微博关注B”。答案只可能是YES（A关注B）或者NO（A不关注B）。
1） 在一群共n个人中，可能有多少个名人？
2） 请设计一个算法找出名人(你可以很容易地得出一个基于遍历的算法，然后尝试改进它)。
3.7　（最大和连续子序列）　给定一个由一些整数组成的序列S，请找出和最大的连续子序列。例如，S={－2,11,－4,13,－5,－2}，得到的结果应为20=11－4+13。
1） 你可以基于简单遍历数组元素，设计一个复杂度为O(n3)的算法。
2） 改进上述算法中的冗余计算，你可以得到一个复杂度为O(n2)的基于遍历的算法。
3） 基于分治策略(详见第三部分的讨论)，你可以设计一个复杂度为O(n log n)的算法。
4） 分析遍历算法中的冗余计算，你可以设计一个复杂度为O(n)的算法。
5） 基于动态规划策略(详见第五部分的讨论)，你同样可以得到一个复杂度为O(n)的动态规划算法。