一般的な動的配列の実装では、新しい要素のための空きがない場合にスタックを2倍にします。この倍増の場合、プッシュ操作の平均時間はO（n）です。スタックの動的配列実装の複雑さ
倍増の代わりに、（n + k）だけスタックサイズを増加させた場合のプッシュの複雑さは何ですか？そのスタックが空であると仮定すると
に従い、K = 10で、我々は10個の要素にスタックを増やすよう
私のアプローチがあります。 10個の要素の後に、20個の要素となるようにします。周りの要素をコピーする
平均時間は、プッシュため
だから平均時間はO（N）のオーダーでなければならない... 10 + 20 + 30 +ですか？
私のアプローチは正しいですか？
どのようにストレージを増やし、kは十分に小さいかによって、すべての場合やその他の場合はO（1）になる可能性があります。
つまり、管理言語では、サイズn + kの新しい配列を作成し、古い配列（サイズnの）を新しいものにコピーし、最後に古い新しい配列に配列します。 O（1）（配列作成、それは前提）+ O（n）（データコピー）+ O（1）（参照変更）です。非常に実装に依存するため、ガベージコレクタの実行は無視されます。管理されていない言語では、reallocと同様のものを使用して、新しい記憶域が同じメモリ領域を占有し、必要な項目の数だけ拡張されるため、コピーする必要なしに古い要素が保持される。この場合、すべてのケースでO（1）です。ただし、メモリの断片化のためにストレージを必要な数だけ拡張することは不可能であるため、管理された言語のようなアプローチが採用されます（暗黙のうちにrealloc実装によって行われます）。このために、複雑さは管理された言語と同じです：O（n）。
これは実用的な観点からの答えです。上記の答えを使用して分析的観点から答えを見つけることができれば幸いです。がんばろう。
計算が正しくありません。動的配列の典型的な実装がそのサイズを2倍にする（または、より一般的には、サイズをxパーセントだけ増加させる）理由があります。
あなたは1からnまでのサイズを拡張した場合= 2 I、あなたは1 + 2 + 4 + 8 + 16 + ... + 2 私でコピー元素の総量。これを合計すると、2 i + 1より小さくなるため、合計時間複雑度はO（n）であり、1つの挿入のamortized time complexityはO（1）です。 nが2の累乗でない場合、計算はやや複雑になりますが、結果は同じになります。
一方、0からn = i * kまでのサイズをkだけ大きくすると、コピーする要素の総数はk + 2k + 3k + ... + ikになります。これを合計すると、（ik + k）*（ik/k）/ 2 = O（n ）になります。そして、1つの挿入の償却された複雑さはO（n）になります。
このため、ソリューションはサイズを2倍にするよりはるかに悪いです。