小優 發問時間: 社會與文化語言 · 1 0 年前

演算法題目求詳解

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

    http://chern.ie.nthu.edu.tw/alg2003/Suppl_3_rec-so... or

    http://en.wikipedia.org/wiki/Master_theorem.

    圖片參考:http://tw.yimg.com/i/tw/ugc/rte/smiley_35.gif

    參考資料: Leslie's ALGORITHM lecture notes
    • 登入以對解答發表意見
還有問題?馬上發問,尋求解答。