CLRS Chapter4続き

CLRS

Introduction to Algorithms / アルゴリズムイントロダクション
分割統治法。Strassenの行列積のアルゴリズム。再帰方程式の解き方。

Exercise 4.2-1

紙に書いた

Exercise 4.2-2

本の通りに計算するだけ

Theta(n^3)の普通の分割統治法行列積アルゴリズムと実行時間を比較したところ、n=2^6とn=2^7の間でcrossoverが起きた。

Exercise 4.2-3

偶数*偶数正方行列になるように0をパディングする。
T(n) = 7T(\lceil n/2 \rceil) + \Theta(n^2)
なのでMaster methodより計算量は\Theta(n^{\lg 7})

Exercise 4.2-4

\log_3 k \;<\; \log_2 7
を満たす最大のkは21
\Theta(n^{\log_3 21})

Exercise 4.2-5

70x70のものが一番速い。漸近的にはStrassenのものよりどれも速いが、定数項はでかそう。

Exercise 4.2-6

kn^{\lg 7}
k^2n^{\lg 7}

Exercise 4.2-7

P1 = (a + b)(c - d) = ac - ad + bc - bd
P2 = bc
P3 = ad
ac-bd = P1 - P2 + P3
ad+bc = P2 + P3

Exercise 4.3-1 - 4.3-7

紙に書いた

Exercise 4.3-8

n^2じゃなくて、n^2lg(n)だと思うんだけど・・・

Exercise 4.3-9

(\lg n)^{\lg 3}

それ以降

暗算するか紙に書いた
Exercise 4.4-5が難しい。