漸近的計算量

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回「以下」は片方の部分列が空になれば比較しないためです．