答えだけでなく、物事がどのように機能するかを理解したいと思っています。私が持っているものを答えていますが、よくわかりませんし、テキストにはこの種の分析についてはあまり説明されていません。
これがスタックを実装する方法ではないことは十分承知していますが、これが私たちが与えられたシナリオです。
パートA
スタックを表す N 個の整数を含む (ソートされていない) 配列 a のスロット a[0] への挿入の最悪の場合、平均的な場合、および最良の場合の実行時間はどれくらいですか? シータ範囲を指定します。
パートB
すべての挿入が a[0] で行われる場合、スタックを表す最初は空の配列 a への N 個の整数の挿入の償却実行時間は? タイトな O バウンドを与えて、答えを説明してください。
インストラクターは、すべての挿入を a[0] に行っていること、およびこの「スタック」からの削除がないことを明確に示しました。
私の分析はこうです
仮定: a.length >> N
最良のケースは、空の「スタック」に挿入するときに発生する Theta(1) です。
最悪のケースは Theta(N) です。これは、挿入プロセスの一部として、a[0] の場所を空けるために N-1 要素をシフトする必要があるためです。
平均的なケースも Theta(N) です。なぜなら、常に N-1 要素をシフトする必要があるからです。
償却ケース
各挿入コストは (N-1) で、N 個の要素があるため、以下を使用します。
N
Sum (i) = [ N(N+1) ] / 2 = N^2 / 2 which is O(N^2) for N insertions
i=1
償却コストは、N^2 / N = O(N) になります。
私が抱えている問題は、これが簡単に見えることです。私は何かを見逃していますか、それともほとんど死んでいますか?