# 演算法題目求詳解

V. Pan has discovered a way of multiplying 68X 68 matrices using 132,464 multiplications, a way of multiplying 70 X70 matrices using 143,640 multiplications, and a way of multiplying 72 X72 matrices using 155,424 multiplications. Which method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm? Compare it with the running time for Strassen's algorithm.

### 1 個解答

• Leslie
Lv 7
1 0 年前
最佳解答

SOLUTION:

The strassen's divide-and-conquer algorithm for matrix multiplication

has the recurrence for its time complexity

(considering only the counts of scalar multiplications):

T(n) = 7 T(n/2), with the solution

T(n) = O(n^log(2,7)) = O(n^2.807355...)

If, just like Strassen's algorithm, we divide an

nxn matrix into smaller matrices (recursively),

but each with size (n/68)x(n/68), then

when two 68x68 matrices can be multiplied by

132464 scalar multiplications, we'll have the recurrence

T(n) = 132464 T(n/68).

Similarly, the other two ways will have their recurrence:

T(n) = 143640 T(n/70) and

T(n) = 155424 T(n/72), respectively.

The solutions are (respectively) (with big O sign omitted)

n^log(68, 132464) = n^2.795128...,

n^log(70, 143640) = n^2.795122..., and

n^log(72, 155424) = n^2.795147....

So, the 2nd method is the fastest (in theory), and

all of the three Victor Y. Pan's algorithms are better than

Strassen's.

Notes:

(1) I used log(b, v) to mean "log v with base b".

(2) The solution to the recurrence T(n) = a T(n/c) is

n^(log(c, a)) in our case, which is covered by

the "Master Theorem". See Theorem 3.1 on

參考資料： Leslie's ALGORITHM lecture notes
• 登入以對解答發表意見