《算法导论》课后习题 4.2

《算法导论》课后习题

4.2-3 How would you modify Strassen’s algorithm to multiply n×n matrices in which n is not an exact power of 2? Show that the resulting algorithm runs in time Θ(n^ lg7)

答： Ⅰ 只需要用0将 n × n 的原矩阵扩充为 2^ k × 2^ k 矩阵就可 Ⅱ 证明运行时间仍为Θ(n^ lg7):

需要注意，n不是2的幂的话，那就必定落在(2^ k-1, 2^ k)区间之内； 也就是存在k，使得 2^ k-1 < n < 2^ k 那么将n × n矩阵扩充为 2^ k × 2^ k+1 矩阵，代价为O(n) 其它操作divide、conquer和combine都不变 T(n) = Θ(n' ^ lg7) + O(n) Θ(n ^ lg7) < Θ(n' ^ lg7) < Θ((2n) ^ lg7) = Θ(n ^ lg7) ⇒ T(n) = Θ(n ^ lg7) proved

4.2-4 What is the largest k such that if you can multiply 3×3 matrices using k multiplications (not assuming commutativity of multiplication), then you can multiply n×n matrices is time o(n^ lg7)? What would the running time of this algorithm be?

分析：2 × 2 矩阵乘法最少需要7次乘法，所以Strassen’s algorithm running time is Θ(n ^ lg7)；现在假设 3 x 3 矩阵乘法可以最少用到k次乘法，所以可以直接猜测要求的 algorithm running time is Θ(n ^ log3k)；

running time of this algorithm: T(n) = k * T(n / 3) + Θ(n ^ 2) 要求最大的k，即令 n ^ log3k < n ^ lg7 log3 k < log2 7 有 k = 21