算法导论第三版，学习日志，2.思考

2-1（在归并排序中对小数组采用插入排序）虽然归并排序的最坏情况运行时间为 Θ(n lg n)，而插入排序的最坏情况运行时间为 Θ(n²)，但是插入排序中的常量因子可能使得它在 n 较小时，在许多机器上实际运行得更快。因此，在归并排序中当子问题变得足够小时，采用插入排序来使递归的叶变量是有意义的。考虑对归并排序的一种修改，其中使用插入排序来排序长度为 k 的 n/k 个子表，然后使用标准的合并机制来合并这些子表，这里 k 是一个特定的值。a. 证明：插入排序最坏情况可以在 Θ(nk) 时间内排序每个长度为 k 的 n/k 个子表。
b. 表明在最坏情况下如何在 Θ(n lg (n/k)) 时间内合并这些子表。
c. 假定修改后的算法的最坏情况运行时间为 Θ(nk+n lg (n/k))，要使修改后的算法与标准的归并排序具有相同的运行时间，作为 n 的一个函数，借助 Θ 记号，k 的最大值是什么？
d. 在实践中，我们应该如何选择 k？

我的答案与思考：

证明a：

长度为 k 的 n/k 个子表。

每个子表在最坏情况下：

O(k^2)

共有n/k 个子表，所以总时间复杂度为：

O(k^2*n/k)= O(kn)= O(nk)

证明b：

在每一层的元素个数都为n，n/k * k = 2，合并需要遍历每个元素，并比较子表（时间为常数O(1)），因此每一层的时间复杂度为O(n)，而一共有lg(n/k)层，因此需要O(n*lg(n/k))时间合并。

证明c：

Θ(nk+n lg (n/k))=O(nlgn)

k+lg(n/k) = lg n

k + lgn -lgk = lgn

k = lgk

k=1时，1 !=0

k=2时，2!=1

k=4时，4!=2

…

d ：

尽量选中最大的k

Deepseek分析：

a.证明插入排序最坏情况可以在 Θ(nk) 时间内排序每个长度为 k 的 n/k 个子表。
每个子表长度为 k，插入排序最坏情况时间为 Θ(k²)。共有 n/k 个子表，因此总时间为 Θ(k² · n/k) = Θ(nk)。

b.表明在最坏情况下如何在 Θ(n lg (n/k)) 时间内合并这些子表。
合并过程使用标准的归并排序合并机制。初始时有 n/k 个已排序的子表，每个长度为 k。合并这些子表类似于归并排序的递归树，树高为 lg(n/k)（因为每次合并子表数量减半），每层需要处理所有 n 个元素（比较和移动），因此总时间为 Θ(n lg(n/k))。

c.要使修改后的算法与标准归并排序具有相同的运行时间 Θ(n lg n)，需满足 Θ(nk + n lg(n/k)) = Θ(n lg n)。
两边除以 n 得：k + lg(n/k) = Θ(lg n)。进一步分解：k + lg n - lg k = Θ(lg n) ⇒ k - lg k = Θ(0)。这意味着 k 必须满足 k = O(lg n)，且 lg k = o(lg n)（即 k 的增长慢于多项式增长）。当 k = Θ(lg n) 时，nk = Θ(n lg n)，且 n lg(n/k) = Θ(n lg n)，总时间为 Θ(n lg n)。若 k 比 lg n 增长更快（如 k = (lg n)²），则 nk 项占主导，总时间超过 Θ(n lg n)。因此，k 的最大值为 Θ(lg n)。

d.在实践中，k 的选择应通过实验确定：在目标机器上测试不同 k 值下排序的性能，选择使运行时间最小的 k。通常 k 取值在 10 到 20 之间。

2-2（冒泡排序的正确性） 冒泡排序是一种流行但低效的排序算法，它的作用是反复交换相邻的未按次序排列的元素。BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A[j] < A[j - 1]
4 exchange A[j] with A[j - 1]a. 假设 A′ 表示 BUBBLESORT(A) 的输出。为了证明 BUBBLESORT 正确，我们必须证明它将终止并且有：
A′[1] ≤ A′[2] ≤ ⋯ ≤ A′[n] (2.3)
其中 n = A.length。为了证明 BUBBLESORT 确实完成了排序，我们还需要证明什么？下面两部分将证明不等式(2.3)。b. 为第 2~4 行的 for 循环精确地说明一个循环不变式，并证明该循环不变式成立。你的证明应该使用本章中给出的循环不变式证明的结构。c. 使用(b)部分证明的循环不变式的终止条件，为第 1~4 行的 for 循环说明一个循环不变式，该不变式将使你能证明不等式(2.3)。你的证明应该使用本章中给出的循环不变式证明的结构。d. 冒泡排序的最坏情况运行时间是多少？与插入排序的运行时间相比，其性能如何？

我的答案与思考：

a.冒泡排序，是通过一直比较相邻元素，如果满足条件，就将其放到正确的位置，如要求后面元素小于前面元素就会交互位置，每次循环，会利用这个机制，如果遇到数组中的最小值，会一直交互位置直到停止位置，因此可以通过两次循环，外层循环，是确定停止位置，内层循环是将停止位置后面的元素进行相邻元素交互，最终将最小值带过来。

证明每次外层循环都能将最小值放在最前面。

b.循环不变式为，A[j]为A[j..n]的最小值。

初始，j=n，A[j..n]中只有一个元素，A[j]确实是A[j..n]中的最小值，满足。

每次循环前，通过一直交互顺序，如果有一个值为A[j..n]中的最小值，那它就一直满足条件，一直被搬运到A[j]的位置，所以满足。

终止，j为中i+1，将A[j..n]中最小值，搬运到A[i+1]位置，满足条件。

c.根据b中循环不等式的终止条件，所以第 1~4 行的循环不等式为：A[i]为A[1..i]中的最大值。

初始，i=1，A[1..i]中只有A[1]一个元素，满足为最大值的条件。

每次循环前：经过前一次循环，已经将当前A[i-1..n]中最小值搬运到A[i-1]中了，因此A[i-1]为A[i-1..n]中最小值，A[1..i-1]中最大值，满足。

终止，已排好序，i=n-1，满足A[n-1]为A[1..n-1]中的最大值。

d.第一次外层循环，内层循环需要n次，…最后一次，需要2次。共有2+3+4+5+…+n次，(n-1)(n+2)/2，

因此为O(n^2)与插入排序相同。

Deepseek分析：

a.除了证明输出满足 A′[1] ≤ A′[2] ≤ ⋯ ≤ A′[n]，还需证明输出序列是输入序列的一个排列（即元素相同，仅顺序改变）。

b.内层循环（2~4行）的循环不变式：
在每次迭代开始时，A[j] 是子数组 A[j..n] 中的最小元素。
证明：

• 初始化：j = A.length，子数组 A[j..n] 仅含 A[j]，显然成立。

• 保持：假设迭代前 A[j] 是 A[j..n] 的最小元素。比较 A[j] 和 A[j-1]，若 A[j] < A[j-1]，则交换，使得 A[j-1] 变为原来 A[j] 和 A[j-1] 中的较小值。由于原来 A[j] 是 A[j..n] 的最小值，交换后 A[j-1] 比原 A[j-1] 小，且比 A[j..n] 中其他元素小（因为原 A[j] 最小）。然后 j 减 1，新的 A[j]（即原 A[j-1]）可能不是 A[j..n] 的最小值，但注意下一次迭代将比较新的 A[j] 和 A[j-1]，继续将最小值前移。实际上，内层循环的目标是在结束时使 A[i] 成为 A[i..n] 的最小值，该不变式需配合外层循环理解。

• 终止：j = i+1，迭代后 A[i] 成为 A[i..n] 的最小值。

c.外层循环（1~4行）的循环不变式：
在每次迭代开始时，子数组 A[1..i-1] 包含原数组中最小的 i-1 个元素，且已按非降序排列。
证明：

• 初始化：i = 1，A[1..0] 为空，成立。

• 保持：假设迭代前 A[1..i-1] 包含最小的 i-1 个元素且已排序。内层循环结束后，A[i] 是 A[i..n] 的最小元素，因此 A[i] 大于等于 A[1..i-1] 中的所有元素，且小于等于 A[i+1..n] 中的所有元素。故 A[1..i] 包含最小的 i 个元素且已排序。

• 终止：i = A.length，A[1..n] 包含全部元素且已排序。

d.冒泡排序的最坏情况运行时间为 Θ(n²)，与插入排序相同。但实际中冒泡排序通常更慢，因为其交换操作更多。

2-3（霍纳（Horner）规则的正确性） 给定系数 a₀, a₁, ⋯, aₙ 和 x 的值，代码片段
1 y = 0
2 for i = n downto 0
3 y = aᵢ + x·y
实现了用于求值多项式
P(x) = ∑{k=0}^{n} a_k x^k = a₀ + x(a₁ + x(a₂ +⋯ + x(a{n-1} + x a_n)⋯))
的霍纳规则。

我的答案与思考

a. 借助 Θ 记号，实现霍纳规则的以上代码片段的运行时间是多少？

一共是n次，每次内部循环是常数时间操作，因此时间复杂度为O(n)
b. 编写伪代码来实现朴素的多项式求值算法，该算法从头开始计算多项式的每个项。该算法的运行时间是多少？与霍纳规则相比，其性能如何？

int polynomial_evaluation(std::vector<int>& A, int x) { int sum = 0; int v = 0; for (int i = 0; i < A.size(); i++) { v = 1; if (i != 0) { v = x; for (int j = 0; j < i - 1; j++) { v *= x; } } sum+= A[i] * v; } return sum; }

一共n次循环，内部是a次运行

如果n大于2时

1+1+2+3+4+5+..+n

(n+2)(n-2)/2 + 2

n^2-2

O（n^2）比霍纳规则效率低的多
c. 考虑以下循环不变式：
在第 2～3 行 for 循环每次迭代的开始有
y = ∑{k=0}^{n-(i+1)} a{k+i+1} x^k
把没有项的和式解释为等于 0。遵照本章中给出的循环不变式证明的结构，使用该循环不变式来证明终止时有
y = ∑_{k=0}^{n} a_k x^k

起始：i=n，y=0，正确。

每次循环开始时：y=a(i+1)+a(i+2)x+….a(n)x^n-(i+1)，正确。

终止：i=0，y=a1x^1+….akx^k，正确。
d. 最后证明上面给出的代码片段将正确地求由系数 a₀, a₁, ⋯, aₙ 刻画的多项式的值。

空。

Deepseek分析：

a.运行时间为 Θ(n)。循环迭代 n+1 次，每次执行常数时间操作。

b.朴素多项式求值算法伪代码：

NAIVE-POLY-EVAL(A, x) 1 y = 0 2 for i = 0 to n 3 term = 1 4 for j = 1 to i 5 term = term * x 6 y = y + A[i] * term 7 return y

运行时间为 Θ(n²)（因为内层循环计算 x^i 需要 i 次乘法）。霍纳规则仅需 Θ(n)，性能更优。

c.循环不变式证明：

• 初始化：i = n，y = 0，右边求和为空（定义为 0），成立。

• 保持：假设迭代开始时 y = ∑{k=0}^{n-(i+1)} a{k+i+1} x^k。执行 y = a_i + x·y 后，
  y = a_i + x·∑{k=0}^{n-(i+1)} a{k+i+1} x^k
  = a_i + ∑{k=0}^{n-(i+1)} a{k+i+1} x^{k+1}
  = a_i + ∑{k=1}^{n-i} a{k+i} x^k
  = ∑{k=0}^{n-i} a{k+i} x^k。
  i 减 1 后，下一次迭代开始时的 i' = i-1，右边求和为 ∑{k=0}^{n-(i'+1)} a{k+i'+1} x^k = ∑{k=0}^{n-i} a{k+i} x^k，与上式一致，不变式保持。

• 终止：i = -1，此时 y = ∑_{k=0}^{n} a_k x^k，得证。

d.根据 c 中的证明，代码正确实现了霍纳规则，能正确求值多项式。

2-4（逆序对）假设 A[1..n] 是一个有 n 个不同数的数组。若 i < j 且 A[i] > A[j]，则对偶 (i, j) 称为 A 的一个逆序对（inversion）。

我的答案与思考：

a. 列出数组 (2, 3, 8, 6, 1) 的 5 个逆序对。

2，1

3，1

8，1

6，1

8，6
b. 由集合 {1, 2, ..., n} 中的元素构成的什么数组具有最多的逆序对？它有多少逆序对？

最多有n-1+n-2+…+1

n(n-1)/2个

它有0个
c. 插入排序的运行时间与输入数组中逆序对的数量之间是什么关系？证明你的回答。

插入排序的运行时间与数组中逆序对的数量正相关。

插入排序中，内层循环，进入条件有需要保证A[i]>A[j]，且i<j正好和逆序对中的若 i < j 且 A[i] > A[j] 一样，也就是说，存在逆序对才能进入内层循环。
d. 给出一个确定在 n 个元素的任何排列中逆序对数量的算法，最坏情况需要 Θ(n lg n) 时间。（提示：修改归并排序。）

void merge(std::vector<int>& A, int p, int q, int r) { std::vector<int> L(A.begin() + p, A.begin() + q + 1); std::vector<int> R(A.begin() + q + 1, A.begin() + r + 1); int i = 0, j = 0; for (int k = p; k <= r; k++) { if (i == L.size()) { A[k] = R[j]; j++; } else if (j == R.size()) { A[k] = L[i]; i++; } else if (L[i] <= R[j]) { A[k] = L[i]; i++; } else { A[k] = R[j]; j++; } } } void merge_sort(std::vector<int>&A, int p, int r ) { if (p < r) { int q = (p + r) / 2; merge_sort(A, p, q); merge_sort(A, q + 1, r); merge(A, p, q, r); } } int main() { std::vector<int> n1 = { 5,2,4,7,1,3,2,6 }; auto n2 = n1; int n = 0; merge_sort(n1, 0, n1.size() - 1); for (int i = 0; i < n1.size(); i++) { if (n1[i] != n2[i]) { n++; } } std::cout << "n = " << n << std::endl; return 0; }

时间复杂度O(lgn * n + n) = O(nlgn)

Deepseek分析：

a.数组 ⟨2, 3, 8, 6, 1⟩ 的逆序对：
(2,1), (3,1), (8,1), (6,1), (8,6)。共 5 个。

b.逆序对最多的数组是严格递减的数组，逆序对数为 n(n-1)/2。
严格递增的数组逆序对数为 0。

c.插入排序的运行时间与逆序对数量成正比。
因为插入排序的内层循环每次交换相邻元素，恰好消除一个逆序对，其他操作为常数时间。若逆序对数量为 I，则运行时间为 Θ(n + I)。最坏情况 I = Θ(n²)，运行时间为 Θ(n²)。

d.修改归并排序以计数逆序对：
在合并两个已排序子数组时，若从右子数组取出元素，则左子数组剩余的所有元素均大于该元素，逆序对增加左子数组剩余元素个数。
伪代码：

COUNT-INVERSIONS(A, p, r) 1 if p < r 2 q = ⌊(p + r)/2⌋ 3 left = COUNT-INVERSIONS(A, p, q) 4 right = COUNT-INVERSIONS(A, q+1, r) 5 inv = MERGE-INVERSIONS(A, p, q, r) 6 return left + right + inv MERGE-INVERSIONS(A, p, q, r) 1 n1 = q - p + 1 2 n2 = r - q 3 创建数组 L[1..n1] 和 R[1..n2] 4 for i = 1 to n1 5 L[i] = A[p + i - 1] 6 for j = 1 to n2 7 R[j] = A[q + j] 8 i = 1, j = 1, k = p, inv = 0 9 while i ≤ n1 and j ≤ n2 10 if L[i] ≤ R[j] 11 A[k] = L[i] 12 i = i + 1 13 else 14 A[k] = R[j] 15 j = j + 1 16 inv = inv + (n1 - i + 1) // 左子数组剩余元素个数 17 k = k + 1 18 while i ≤ n1 19 A[k] = L[i] 20 i = i + 1, k = k + 1 21 while j ≤ n2 22 A[k] = R[j] 23 j = j + 1, k = k + 1 24 return inv

运行时间为 Θ(n lg n)。

Deepseek总结：

你的回答大部分正确，但在一些细节上需要完善，尤其是循环不变式的证明和逆序对计数的算法。