在典型的動態數組實現中，當沒有空間存放新元素時，我們將堆棧加倍。在這種情況下，推平操作的平均時間是O（n）。動態數組堆棧實現的複雜性
推動的複雜度是多少？如果不是兩倍，我們增加了堆棧大小（n + k）？
我的方法是如下
假設棧是空的，且k = 10，我們提高堆疊到10個元素。 10個元素之後，我們製作20個元素等等。
平均時間，以圍繞複製元素是10 + 20 + 30 + ...
用於推所以平均時間必須在O（n）的順序？
我的方法是否正確？
根據你將如何增加存儲空間和k是足夠小，它可能是O（1）所有情況下或其他東西。
我的意思是，在託管語言中，可以創建一個新的n + k大小的數組，然後將舊的數組（大小爲n）複製到新的數組中，最後替換舊的數組陣列到新的一個。這將是：O（1）（數組創建，這是一個假設）+ O（n）（數據副本）+ O（1）（參考更改）。我們忽略垃圾回收器的執行，因爲它非常依賴於實現。在非託管語言中，可以使用類似於realloc的東西，以便保留舊元素而不需要複製，因爲新存儲佔用相同的內存區域，只擴展到所需項目的數量。在這種情況下，所有情況都是O（1）。請注意，然而，由於內存碎片，有時將存儲擴展到所需項目的數量是不可能的，所以採取了類似託管語言的方法（但由realloc實現隱含地完成）。對於這個，複雜性與託管語言中的相同：O（n）。
這就是從實際角度出發的答案，我希望你能從上面的答案中以分析的角度找到答案。祝你好運。
您的計算不正確。動態數組的典型實現將其大小加倍（或者更一般地，將其大小增加x百分比）是有原因的。
如果從1生長的大小爲n = 2 我，即複製是1 + 2 + 4 + 8 + 16 + ... + 2 我元素的總量。如果對此進行求和，則它小於2 i + 1，因此總時間複雜度爲O（n），且一個插入的amortized time complexity爲O（1）。如果n不是2的冪，那麼計算會稍微複雜一些，但結果將是相同的。另一方面，如果將大小增加k，從0到n = i * k，則複製的元素總數爲k + 2k + 3k + ... + ik。如果你總結這一點，它將是（ik + k）*（ik/k）/ 2 = 0（n ）。並且一次插入的分期複雜性將是O（n）。
因此，您的解決方案比加倍大小差得多。