我想對動態陣列進行攤銷分析：當我們執行 n 次插入的序列時，每當大小為 k 的陣列填滿時，我們重新分配大小為 k sqrt(k) 的陣列，并復制現有的 k 值進入新陣列。
我是攤銷分析的新手，這是我尚未遇到的問題，因為我們每次都通過不同的非常量值調整陣列的大小。(newSize=prevSize sqrt(prevSize))
總成本應該是 Θ(n*sqrt(n))，因此每次操作是 Θ(sqrt(n))。
我意識到對于某個常數 c，每當 k >= c^2 時，我們的陣列就會增長 c。讓我們從大小為 k=1 的陣列開始（假設 n 足夠大，就本示例而言）。在 n 次插入之后，我們得到了插入 副本的總成本的總和：
1 1(=k) 1 2(=k) 1 3(=k) 1 4(=k) 2 6(=k) 2 8(=k) 2 10(=k) 3 13(=k) 3 16(=k) 4 20(=k) 4 24 4 28 5 33 5 38 6 44 6 50 7… n
我看到了模式，但我似乎無法計算邊界。我正在嘗試使用各種攤銷分析方法來限制這個聚合總和。讓我們以會計方法為例，然后我想我需要 round([k sqrt(k)]\sqrt(k)) 或簡單地 round(sqrt(k) 1) 每次插入硬幣，但它不會添加向上。
我很想得到你的幫助，試圖正確地找到上界和下界 sqrt(n) 。
非常感謝！:)
uj5u.com熱心網友回復：
最簡單的方法是在下一次調整大小之前將每個調整大小操作與緊隨其后的插入集中在一起。
每個塊的成本是 O(k sqrt(k))，每個塊由 O(sqrt(k)) 個操作組成，所以每個操作的成本是 O( (k k 0.5 )/k 0.5 ) = O(k 0.5 1) = O(k 0.5 )
當然，如果 n 是您想要的答案，但由于 k(n) 在 Θ(n) 中，因此 O(k 0.5 ) = O(N 0.5 )。
uj5u.com熱心網友回復：
所以在WhatsApp組回答問題
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359117.html
上一篇：無限排序陣列中二分查找的索引錯誤
下一篇：是鏈表回文嗎？與指向混淆