私は、少なくとも Big Oh 表記法の背後にある理論を理解し始めていると思います。つまり、それは関数の速度が成長する速度を測定する方法です。つまり、大きな O はアルゴリズムの効率を数値化します。しかし、その実装は別のものです。
たとえば、最良のシナリオでは、プッシュ操作とプル操作は O(1) になります。これは、スタックからの削除またはスタックへの追加に必要なステップ数が固定されるためです。値に関係なく、プロセスは同じになります。
プッシュやポップなどの一連のイベントがパフォーマンスを O(1) から O(n^2) に低下させる方法を想像しようとしています。n/2 容量の配列、n プッシュおよびポップ操作、およびフルまたは半分フルのときにその容量を 2 倍または半分にする動的配列がある場合、これらの操作が発生する順序が速度にどのように影響する可能性がありますか?プログラムが完了するのはどれですか？プッシュとポップはスタックの最上位要素で機能するため、定数から O(n^2) に効率がどのように変化するかを理解するのに苦労しています。
前もって感謝します。
動的配列がサイズ変更操作を非常にインテリジェントに行うと想定しています。ただし、そうでない場合は、O(n^2) ランタイムになる可能性があります。配列がいっぱいになったときにサイズが 2 倍になるのではなく、単純にサイズ +1 にサイズ変更されるとします。また、サイズ 1 で始まるとします。最初の要素を O(1) に挿入します。2 番目の要素を挿入するときは、配列のサイズを 2 に変更して、前の値をコピーする必要があります。要素 k を挿入すると、現在のサイズは k-1 であり、サイズを k に変更する必要があり、結果として k-1 個の要素をコピーする必要があります。
したがって、n 個の要素を挿入するには、配列を n-1 回コピーすることになります: O(n) 個のサイズが変更されます。より多くの要素が挿入されると、より多くの要素をコピーする必要があるため、コピー操作も n に線形的に依存します: サイズ変更ごとに O(n) コピー。これにより、ランタイムの複雑さが O(n*n) = O(n^2) になります。
スタックを (たとえば) リンクされたリストとして実装すると、プッシュとポップは常に一定時間 (つまり O(1)) になります。
ランタイムが問題にならない限り、動的配列の実装をスタックに選択することはありません。たまたま、動的配列を構築済みで使用可能にし、より効率的なスタック実装を手元に持っていなかった場合を除きます。ただし、それぞれフルまたは半分空になったときにサイズが変更された配列を使用した場合、そのランタイムは O(1) になりますが、プッシュとポップの数はサイズ変更と O(n ）サイズ変更がある場合（したがって、全体的にO（n））。
実装にバグがない限り、スタックとして使用される動的配列が O(n^2) ほどのパフォーマンスを提供できるケースは考えられません。