progC.pdf progC-s.pdf 記事一覧 |
![]() べき乗の計算 |
progC-s.pdf に「D96%漸近的計算量」を追加しました.
参考資料([n]は本文でも引用):
[1] アルゴリズム解析と計算量
http://www.ieice-hbkb.org/files/06/06gun_03hen_01.pdf#page=11
[2] 計算量 - Security Akademeia
http://akademeia.info/index.php?%B7%D7%BB%BB%CE%CC
[3] 計算複雑性理論 - Wikipedia
http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96
[4] 分割統治法(マージソートまで)
http://www.cs.gunma-u.ac.jp/~nakano/Al/note1.html
[5] コンピュータアルゴリズム2 4. 分割統治法
http://www.logos.t.u-tokyo.ac.jp/~tau/lecture/software/gen/slides/4-divconq.pdf
[6] 高速フーリエ変換 - Wikipedia
http://ja.wikipedia.org/wiki/%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B
補足:(1) 計算量には領域計算量と時間計算量がありますが,前者については言及していません.
(2) [%41]の方法を高速フーリエ変換といいます.漸近的計算量がO(N log N)になることを説明するにはもう少し行数が必要です --- ベクトル要素の並び替えや片方の行列にかかっているスカラー倍の扱いの具体化.
(3) [%1]の(m-1+m)「以下」は b(k)=0 のときは乗算不要のため,[%3]の24回「以下」は片方の部分列が空になれば比較しないためです.
※コメント投稿者のブログIDはブログ作成者のみに通知されます