amortized-analysis - 償却分析の集計方法でO(n)/n=1はどのようになっていますか

Question

O(n)/n=1 は、レッスン 5 のデータ構造に関するコースラ コースの償却分析: 集計方法で指定されている償却分析の集計方法ではどのようになっていますか?

Answer 1

簡潔な答え

O(n)/n = cn/n = c = O(1)

長い答え

単一の操作のコストではなく一連の操作のコストを分析するために、償却分析を使用します。最後のケースでは、漸近解析を使用します (漸近表記には、Theta、Big O、Big Omega、Little O、Little Omega などがあります)。そのシーケンスのコストを理解してください。

その理由は、「通常の」漸近分析を適用すると、たとえば、最悪の場合の分析における漸近上限が悲観的すぎる可能性があるためです。古典的な例は、動的配列への挿入です。動的に割り当てられた配列に要素を挿入し、それがいっぱいになったら、新しい配列 (たとえば、2 倍の大きさ) を定義して、すべての要素をコピーします。ほとんどの挿入は一定時間 (または O(1)) で機能しますが、配列を再定義する必要がある場合は、すべての要素をコピーする必要があるため、線形時間 (O(n)) がかかります。 .

したがって、n 個の要素を挿入し、配列を 1 回だけ再定義する必要がある場合、n 個の操作があり、各操作は最悪の場合 O(n) であるため、最悪の場合の一連の操作のコストは O( n^2)、最悪の場合、操作のほとんどが O(1) であり、そのうちの 1 つだけが O(n) であるという事実を考えると、これは悲観的すぎるようです。

一連の操作の償却コストを (n 回の操作のコスト) / n と定義します。あなたの場合、 n 操作のコストは O(n) です。これは cn (c は定数) に等しいです。Big O 表記の定義により、それを n で割ると、O に等しい c だけが得られます。 (1) 繰り返しますが、c は単なる定数です。