2009年2月22日日曜日

計算機プログラムの構造と解釈 1.2.3


このエントリーをはてなブックマークに追加


時間計算量と領域計算量


よく使うオーダーOは時間計算量(の増加の程度)のこと。
なので一般的に計算量といえば時間計算量のことを指す。
領域計算量はメモリやステップ数、スペースの増加の程度のこと。
シータ¥Thetaと呼ぶ。


領域計算量


十分大きなnの値に対し、
k_{1}f(n) ¥leq R(n) ¥leq k_{2}f(n)なるnと独立な正の定数k_{1},k_{2}があればR(n)は¥Theta (f(n))の増加の程度だといい、
R(n)=¥Theta (f(n))と書く。

fibonacciでは¥Theta (n^2)のステップ数と、¥Theta (n)のスペースを必要とする。
オーダーと同じく、大体の計算量しか計算しない。
3n^2+10n+17ステップが必要なプロセスもすべて¥Theta (n^2)の増加の程度という。





0 件のコメント:

コメントを投稿