算法导论第二章思考题

本文主要是介绍算法导论第二章思考题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2-1

∵ 长度为k的数组

∴ 时间复杂度为 Θ（k²）

∵ 共有n/k个数组

∴ T（n）= n/k * Θ（k²）= Θ（nk）

∵ 2^i = n/k

∴ i = lg（n/k）

∴ 共有 lg（n/k）+ 1层

∵ 每层合并数组花费的时间为 Θ（n）

∴ 合并所有子数组的时间为 Θ（nlg（n/k））

∵ 要与原来归并排序具有相同的运行时间

∴ nlg（n/k）+ nk = c*nlgn

∵ 当k逐渐增大，lg（n/k）逐渐减小

∴ k最大为lgn,此时lg（n/lgn）被忽略

选择插入排序比合并排序快的最大的列表长度

2-2

A’中的元素全部来自于A中变换后的元素。

循环不变式：每次迭代之前，A[j]=min{A[k] | j<=k<=n}，并且子数组A[j..n]中的元素还是最初在A[j..n]中的元素。

初始化：第一次迭代之前j=n，子数组A[j..n]只包含一个元素A[n]，循环不变式显然成立。

保持：迭代一个给定值的j。首先假设此次迭代前循环不变式成立，那么根据循环不变式，A[j]是A[j..n]中最小的元素。第3~4行代码表示如果A[j]<A[j-1]就交换A[j]和A[j-1]，显然这使得A[j-1]成为A[j-1..n]中最小的元素。由于唯一改变子数组A[j-1..n]的操作仅仅是那次可能发生的交换操作，且在迭代开始时，A[j..n]中的元素最初都是在A[j..n]中，所以在迭代开始时A[j-1..n]中的元素最初都是在A[j-1..n]中。然后j自减，准备开始进入下一轮迭代。

终止：循环终止时j=i。根据循环不变式，A[j]=A[i]=min{A[k] | i<=k<=n}，并且A[i..n]中的元素最初都在A[i..n]中。

所以在2~4行的for循环执行结束过后，A[i]将是A[i..n]中最小的元素。

循环不变式：每次迭代之前，子数组A[1..i-1]包含了A[1..n]中前i-1小的所有元素，并且它们是已排好序的。A[i..n]中包含了A[1..n]中余暇的元素。

初始化：第一次迭代之前i=1。子数组A[1..i-1]为空，循环不变式显然成立。

保持：迭代一个给定值的i。首先假设此次迭代前循环不变式成立，那么根据循环不变式，A[1..i-1]包含了A[1..n]中前i-1小的所有元素，并且它们是已排好序的。第一部分已经证明：在执行2~4行的for循环后A[i]是A[i..n]中最小的元素。所以在执行了2~4行的for循环后A[1..i]中就包含了A[1..n]中前i小的所有元素，并且它们已经排好序。子数组A[i+1..n]就包含了n-i个A[1..n]中余下的元素。

终止：循环终止时i=n+1 => i-1=n。所以根据循环不变式，A[1..i-1]óA[1..n]中包含了A[1..n]中前i-1小的元素（即A[1..n]的全部元素），并且它们是排好序的。

所以在1~4行的for循环执行结束过后，A[1..n]将是有序的。

根据第二部分的结论，外层for循环结束后，数组A[1..n]中的元素将是排好序的。故冒泡排序算法是正确的。

最坏情况的运行时间是Θ（n²），性能比插入排序差，在以排好序的数组中插入排序的运行时间是Θ（n），而冒泡排序仍是Θ（n²）。

2-3

Θ（n）

朴素的多项式代码实现

public static int test(int[] arr,int x) {int sum = 0;int v;for(int i = 0;i < arr.length;i++) {v = 1;for(int j = 0;j < i;j++) {v *= x; }sum += v*arr[i];}return sum;}

运行时间是Θ（n²）

与霍纳规则相比，性能差很多

初始化：i = n，y = 0，当i代入循环不变式后y = 0，循环不变式成立

保持：