k.t.
kohsk****@msc*****
2003年 2月 25日 (火) 20:31:37 JST
高橋(k)です。 > 手元の「STL - 標準テンプレートライブラリによるC++プログラミング」 > (デービッド・R・マッサー他) > によると、単なる平均計算量(平均時間)と償却時間を区別しているようです。 > たとえばvectorにpush_backする場合、 > for (int i = 0; i < n; ++i) > vec.push_back(3); > は、n回挿入にO(n)時間なので定数償却なわけですが、これは単なる > 「平均計算量」より強い意味があります。n回連続挿入すると確実にO(n) > 時間に収まるわけですから、例えばqsort()は平均的にO(n log n)である、 > という「平均計算量」よりは強い主張です。 > > 償却時間 = 連続N回の操作にかかる合計時間をNで割ったもの > > だそうです。 > > この訳本では、「償却時間(償却計算量)は定数である」「定数償却である」 > のように訳しています。 つまり、通常、処理は定数時間で、処理の間に見えない負債がたまっていくと。 で、たまにその負債を償却しないといけない時があるので`償却定数時間'ですね。 平均の場合は、通常の処理にかかる時間は解らないけど、無限回繰り返せば平均 値になる、ということですね。 意味が解ったところで、どういう訳語が解りやすいのかが問題。 amortized const time は償却定数時間でいい気がしますが。 amortized O(1) も同じことなので償却定数時間でいいんでしょうか。 -- TAKAHASHI, kohske kohsk****@msc***** takah****@cog***** http://talepan.virtualave.net/
