時間計算量と領域計算量
よく使うオーダーは時間計算量(の増加の程度)のこと。
なので一般的に計算量といえば時間計算量のことを指す。
領域計算量はメモリやステップ数、スペースの増加の程度のこと。
シータと呼ぶ。
領域計算量
十分大きなnの値に対し、なるnと独立な正の定数
があればR(n)は
の増加の程度だといい、
R(n)=と書く。
fibonacciではのステップ数と、
のスペースを必要とする。
オーダーと同じく、大体の計算量しか計算しない。
3n^2+10n+17ステップが必要なプロセスもすべての増加の程度という。
0 件のコメント:
コメントを投稿