算法练习与实现：从中位数查找至矩阵乘法

### 算法练习与实现：从中位数查找至矩阵乘法 #### 1. 中位数查找相关问题 - **查找数组中最接近中位数的 k 个数**：给定一个包含不同数字的大小为 n 的数组 A 和正整数 k（k ≤ n），需要设计算法找出 A 中最接近中位数的 k 个数。 - **两个有序数组的中位数**：对于两个有序数组 A[1..n] 和 B[1..n]，要设计算法找出这 2n 个元素的中位数，并分析其运行时间。 - **快速排序以中位数为枢轴的比较次数**：若数组大小为 n，中位数是第 ⌈n/2⌉ 小的值。当快速排序总是选择中位数作为枢轴元素时，分析最坏情况下的比较次数。 #### 2. 整数乘法算法 ##### 2.1 分治法整数乘法 - **算法描述**：假设 n 是 2 的幂，将两个数 u 和 v 拆分为 u = x × 10^(n/2) + y 和 v = w × 10^(n/2) + z。则乘积为 A × 10^n + (B + C) × 10^(n/2) + D，其中 A = x × w，B = y × w，C = x × z，D = y × z。以下是递归算法： ```plaintext Multiply(u, v): (1) 假设 n = length(u) = length(v)，可对较短数字补 0 (2) 如果 length(u) 和 length(v) 为 1，则返回 u × v (3) 将 u, v 拆分为 u = x × 10^(n/2) + y 和 v = w × 10^(n/2) + z (4) A = Multiply(x, w) (5) B = Multiply(y, w) (6) C = Multiply(x, z) (7) D = Multiply(y, z) (8) 返回 A × 10^n + (B + C) × 10^(n/2) + D ``` - **运行时间分析**：设 T(n) 是两个 n 位数字相乘的运行时间，可证明 T(n) = 4T(n/2) + O(n)。 - **示例计算**：以 4301 × 2021 为例，按照上述算法进行乘法计算。 ##### 2.2 改进的分治法整数乘法 - **算法描述**： ```plaintext Multiply(u, v): (1) 假设 n = length(u) = length(v)，可对较短数字补 0 (2) 如果 length(u) ≥ 1，则返回 u × v (3) 将 u, v 拆分为 u = x × 10^(n/2) + y 和 v = w × 10^(n/2) + z (4) A = Multiply(x, w) (5) B = Multiply(y, z) (6) C = Multiply(x + y, z + w) (7) 返回 A × 10^n + (C - A - B) × 10^(n/2) + B ``` - **运行时间分析**：可证明 T(n) = 3T(n/2) + O(n)。 ##### 2.3 拆分为三部分的整数乘法 - **算法描述**：将两个 n 位（n 是 3 的幂）整数 x 和 y 分别拆分为三部分，x 拆为 a, b, c，y 拆为 d, e, f，每部分有 n/3 位。则 xy 的计算可通过一系列中间结果 r1 - r6 得到： ```plaintext r1 := ad r2 := (a + b)(d + e) r3 := be r4 := (a + c)(d + f) r5 := cf r6 := (b + c)(e + f) z := r12^(4n/3) + (r2 - r1 - r3)2^n + (r3 + r4 - r1 - r5)2^(2n/3) + (r6 - r3 - r5)2^(n/3) + r5 ``` - **正确性证明**：需要证明 z = xy。 - **示例计算**：以 4301 × 2021 为例，使用该分治法算法进行乘法计算。 - **运行时间分析**：可证明该算法的运行时间为 O(n^1.63)。 #### 3. 多项式乘法 - **朴素算法**：对于两个多项式 A(x) = a0 + a1x + a2x^2 + · · · + anx^n 和 B(x) = b0 + b1x + b2x^2 + · · · + bnx^n，可设计朴素算法计算它们的乘积 C(x) = A(x) × B(x)。 - **分治法算法**：给出两种分治法算法来计算多项式乘法。 - **减少乘法次数的方法**：对于多项式 A = ax + b 和 B = cx + d，可通过仅三次乘法完成 A × B 的计算，提示其中一次乘法为 (a + b)(c + d)。 #### 4. 矩阵乘法 ##### 4.1 朴素矩阵乘法算法 ```plaintext Procedure matrixMultiply(X, Y, n); Comment 相乘 n×n 矩阵 X 和 Y 1. for i:=1 to n do 2. for j:=1 to n do 3. Z[i, j] := 0; 4. for k :=1 to n do 5. Z[i, j] := Z[i, j] + X[i, k].Y[k, j]; 6. return (Z) ``` - **正确性证明**：需要证明该矩阵乘法算法的正确性。 - **运行时间分析**：分析该算法在最坏情况下的乘法次数。 ##### 4.2 分治法矩阵乘法算法 ```plaintext MMult(A, B, n): (1) 如果 n = 1 输出 A × B (2) 否则 (3) 计算 A11, B11, …, A22, B22 (4) X1 ← MMult(A11, B11, n/2) (5) X2 ← MMult(A12, B21, n/2) (6) X3 ← MMult(A11, B12, n/2) (7) X4 ← MMult(A12, B22, n/2) (8) X5 ← MMult(A21, B11, n/2) (9) X6 ← MMult(A22, B21, n/2) (10) X7 ← MMult(A21, B12, n/2) (11) X8 ← MMult(A22, B22, n/2) (12) C11 ← X1 + X2 (13) C12 ← X3 + X4 (14) C21 ← X5 + X6 (15) C22 ← X7 + X8 (16) 输出 C (17) 结束条件语句 ``` - **示例计算**：以矩阵 ```plaintext A = ⎛ ⎜⎜⎝ 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 ⎞ ⎟⎟⎠ B = ⎛ ⎜⎜⎝ 9 8 7 5 2 3 1 5 6 6 3 4 7 9 1 2 ⎞ ⎟⎟⎠ ``` 为例，使用上述算法进行矩阵乘法。 - **运行时间分析**：设 T(n) 是 MMult(A, B, n) 执行的数学运算总数，可证明 T(n) = 8T(n/2) + Θ(n^2)。 ##### 4.3 Strassen 矩阵乘法算法 ```plaintext Strassen(A, B): (1) 如果 n = 1 输出 A × B (2) 否则 (3) 计算 A11, B11, …, A22, B22 (4) P1 ← Strassen(A11, B12 - B22) (5) P2 ← Strassen(A11 + A12, B22) (6) P3 ← Strassen(A21 + A22, B11) (7) P4 ← Strassen(A22, B21 - B11) (8) P5 ← Strassen(A11 + A22, B11 + B22) (9) P6 ← Strassen(A12 - A22, B21 + B22) (10) P7 ← Strassen(A21 ```