数値解析 第11回 (6) 計算量の見積もり
四則演算の計算量
計算機システム学等で習っていると思いますが
Th.4 $m$ ビットの数同士の四則演算の計算量は
- 加算・減算は $O(m)$
- 乗算・除算は $O(m^2)$
証明 加算は、
半加算器と全加算器 を
$m$ 個つないで逐次処理しますので $m$ に比例した実行時間が掛かります。
減算は 2 の補数との加法なので、やはり $O(m)$。
乗算と除算は、筆算を思い浮かべれば、$m$ ビットの加算・減算を最大 $m-1$ 回繰り返しますので $O(m)\times O(m)=O(m^2)$ となります。
(証明終)
従って
今日の 2 ページ目 で述べたように
加減乗除で構成されているプログラムの実行時間は、その中の乗算・除算の回数で見積ることができる
ことになります。
乗算・除算の回数の見積もり
LU分解法の Step 1 ver.1 を例に挙げて、
アルゴリズムの中の乗算・除算回数の見積もり方を説明します。
難しいことはありません。
- 式は、その中の乗算・除算の個数に置き換えます
- for 文は、正確には $\sum$ に置き換えるべきですが、ルーズに $\dps{\int}$ で置き換えます
やってみましょう。
$\require{color}$
Algorithm ( Step 1 ) ver.1
for $\textcolor{red}{i=1}$ to $\textcolor{red}{n}$
for $\textcolor{blue}{j=1}$ to $\textcolor{blue}{i}$
$\textcolor{orange}{\ell_{ij}=a_{ij}-\dps{\sum_{k=1}^{j-1} \ell_{ik}\,u_{kj}}}$
for $\textcolor{green}{j=i+1}$ to $\textcolor{green}{n}$
$\textcolor{purple}{\dps{u_{ij}=\left(a_{ij}-\sum_{k=1}^{i-1} \ell_{ik}\,u_{kj}\right)\,/\,\ell_{ii}}}$
制御変数 $i$ の for 文は $i$ での積分、
制御変数 $j$ の for 文は $j$ での積分に置き換えます。
オレンジ色の式は $j-1$ 個の乗算、
紫色の式は $i-1$ 個の乗算とひとつの除算が使われていますので、
乗算・除算の回数はおおよそ
$\dps{
\textcolor{red}{\int_1^n} \left(\textcolor{blue}{ \int_1^i} (\, \textcolor{orange}{j-1} \,) \, \textcolor{blue}{dj}
+ \textcolor{green}{\int_{i+1}^n} (\, \textcolor{purple}{(i-1)+1} \,) \, \textcolor{green}{dj} \right) \textcolor{red}{di}}$
≒ $\dps{\int_0^n \left( \int_0^i j\, dj + \int_{i}^n i\, dj \right) di}$
≒ $\dps{\int_0^n \left( \frac{i^2}{2} + (n-i)i\right) di
= \frac{n^3}{6} + \frac{(n-0)^3}{6} = \frac{n^3}{3}}$
となります。