算法导论第三版第二章思考题答案

第二章思考题

• 算法导论第三版第二章思考题答案
• • 2.1
  • 2.2
  • 2.3
  • 2.4
  • 汇总传送门

2.1

#include
using namespace std;
const int N = 1e5 + 10, INF = 2e9, K = 5;
int a[N], L[N], R[N];
void insert_sort(int a[], int l, int r)
{for(int i = l + 1; i <= r; ++i){int v = a[i], j = i - 1;for(; j >= l && a[j] > v; --j) a[j + 1] = a[j];a[j + 1] = v;}
}
void merge(int a[], int l, int mid, int r)
{int n1 = mid - l + 1, n2 = r - mid;for(int i = 1; i <= n1; ++i) L[i] = a[l + i - 1];for(int i = 1; i <= n2; ++i) R[i] = a[mid + i];L[n1 + 1] = R[n2 + 1] = INF;int i = 1, j = 1;for(int k = l; k <= r; ++k){if(L[i] <= R[j]) a[k] = L[i ++];else a[k] = R[j++];}
}
void merge_sort(int a[], int l, int r)
{if(l >= r) return;if(r - l + 1 <= K){insert_sort(a, l, r);return;}int mid = l + r >> 1;merge_sort(a, l, mid);merge_sort(a, mid + 1, r);merge(a, l, mid, r);
}int main()
{int n;cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i];merge_sort(a, 1, n);for(int i = 1; i <= n; ++i) cout << a[i] << " ";cout << endl;return 0;
}

证明：a.插入排序的时间复杂度为O(n2),所以最坏复杂度为(n/k)∗k2=n∗k.b.通过插入排序获得了长度为n/k的有序段，且总长度为n，为了合并回长度为n的段，我们需要两个子序列，并递归的做下去，每次合并都比较了n个元素，所以时间为O(nlg(n/k))c.nk+nlg(n/k)=nlgn,k=O(lgn)证明：\\ a.插入排序的时间复杂度为O(n^2), 所以最坏复杂度为(n/k) * k^2 =n*k.\\ b. 通过插入排序获得了长度为n/k的有序段，且总长度为n，为了合并回\\长度为n的段，我们需要两个子序列，并递归的做下去，每次合并都比较\\了n个元素，所以时间为O(nlg(n/k))\\ c.nk + nlg(n / k) = nlgn,k = O(lgn) 证明：a.插入排序的时间复杂度为O(n2),所以最坏复杂度为(n/k)∗k2=n∗k.b.通过插入排序获得了长度为n/k的有序段，且总长度为n，为了合并回长度为n的段，我们需要两个子序列，并递归的做下去，每次合并都比较了n个元素，所以时间为O(nlg(n/k))c.nk+nlg(n/k)=nlgn,k=O(lgn)

2.2

a.A′的所有元素是A中所有元素不重不漏的有序排列。b.循环不变式:每次迭代开始前，aj都是a[j:n]中最小的元素。证明如下：初始；当j=A.length,a[A.length:A.length]只有末尾单独元素，成立.保持:当j!=A.length,每次迭代我们都把较大的数字交换到左边的位置，所以aj始终是最小的。终止:最后一次迭代结束后，j=i,此时ai是a[i:n]最小的元素成立。c.循环不变式:每次迭代开始前，ai−1都是第i−1小的.证明如下：初始：当i=1，i−1=0，为空，所以成立。保持：每次迭代开始前，由b中的终止结论可知，上一次关于i的迭代使得ai−1成为了a[i−1:n]中最小的那个元素。所以每次迭代开始前，ai−1都是第i−1小的。终止：当最后一次迭代结束后，i=A.length,此时a[1:n−1]由前面的分析已经有序且是前i−1小，所以最后一个元素是最大的，也就是不等式2−3所说的。d.O(n2)，同插入排序。a. A'的所有元素是A中所有元素不重不漏的有序排列。\\ b. 循环不变式: 每次迭代开始前，a_j都是a[j:n]中最小的元素。证明如下：\\ 初始；当j=A.length, a[A.length:A.length]只有末尾单独元素，成立.\\ 保持:当j!=A.length,每次迭代我们都把较大的数字交换到左边的位置，\\所以a_j始终是最小的。\\ 终止:最后一次迭代结束后，j = i, 此时a_i是a[i:n]最小的元素成立。\\ c. 循环不变式:每次迭代开始前，a_{i-1}都是第{i - 1}小的.证明如下：\\ 初始：当i=1，i-1=0，为空，所以成立。\\ 保持：每次迭代开始前，由\\b中的终止结论可知，上一次关于i的迭代使得a_{i-1}成为了a[i-1:n]\\中最小的那个元素。所以每次迭代开始前，a_{i-1}都是第i-1小的。\\ 终止：当最后一次迭代结束后，i=A.length,此时a[1:n-1]由前面的\\分析已经有序且是前i-1小，所以最后一个元素是最大的，也就是不等式\\2-3所说的。\\ d.O(n^2)，同插入排序。 a.A′的所有元素是A中所有元素不重不漏的有序排列。b.循环不变式:每次迭代开始前，aj​都是a[j:n]中最小的元素。证明如下：初始；当j=A.length,a[A.length:A.length]只有末尾单独元素，成立.保持:当j!=A.length,每次迭代我们都把较大的数字交换到左边的位置，所以aj​始终是最小的。终止:最后一次迭代结束后，j=i,此时ai​是a[i:n]最小的元素成立。c.循环不变式:每次迭代开始前，ai−1​都是第i−1小的.证明如下：初始：当i=1，i−1=0，为空，所以成立。保持：每次迭代开始前，由b中的终止结论可知，上一次关于i的迭代使得ai−1​成为了a[i−1:n]中最小的那个元素。所以每次迭代开始前，ai−1​都是第i−1小的。终止：当最后一次迭代结束后，i=A.length,此时a[1:n−1]由前面的分析已经有序且是前i−1小，所以最后一个元素是最大的，也就是不等式2−3所说的。d.O(n2)，同插入排序。

2.3

a.O(n)a.O(n)a.O(n)
b.

for(int i = 0; i <= n; ++i)
{int base = 1;for(int i = 0; i < base; ++i) base *= x;ans += base * a[i];
}

这个是O(n2)O(n^2)O(n2),更慢。
c.i=−1代入即可。d.终止时的式子展开即可。c.i = -1代入即可。\\ d. 终止时的式子展开即可。 c.i=−1代入即可。d.终止时的式子展开即可。

2.4

a.(2,1),(3,1),(8,6),(8,1),(6,1)b.按照降序排列拥有最多的逆序对，S=1+2+..+n−1=n∗n/2c.插入排序花在寻找插入位置的时间与逆序对的数量正相关。每多寻找一次，都代表存在ai>aj，且i a_j，且iaj​，且i d.

LL ans;void merge(int a[], int l, int mid, int r)
{int n1 = mid - l + 1, n2 = r - mid;for(int i = 1; i <= n1; ++i) L[i] = a[l + i - 1];for(int i = 1; i <= n2; ++i) R[i] = a[mid + i];L[n1 + 1] = R[n2 + 1] = INF;int i = 1, j = 1;for(int k = l; k <= r; ++k){if(L[i] <= R[j]) a[k] = L[i ++];else a[k] = R[j++], ans += n1 - i + 1;}
}
void merge_sort(int a[], int l, int r)
{if(l >= r) return;int mid = l + r >> 1;merge_sort(a, l, mid), merge_sort(a, mid + 1, r);merge(a, l, mid, r);
}

汇总传送门

链接: 算法导论习题答案汇总