我試圖製作一個具有隻有兩個級別的恆定間隙大小的「完美」跳過列表。從計算不同大小的跳過列表的訪問節點,我可以看出它是由大小決定的,但我無法用n來計算公式。找到只有兩個級別的確定性跳過列表的最佳間隔大小
-1
A
回答
1
如果您確實需要恆定的間隙大小,那麼您的最佳間隙大小就是列表長度的平方根。例如,如果您的跳過列表長度爲16個項目,則最佳間隔大小爲4.要到達第15個項目,您需要進行3次長跳躍和3次短跳躍。這是最糟糕的情況。
要得到第k個項目,你關注了k/sqrt(n) + k%sqrt(n)
鏈接。
更大的間隙大小會讓你更快地結束,但爲了獲得列表中的某個位置,你可能必須遵循更多的單一鏈接。平均而言,您將遵循更多鏈接。如果間隙較小,則可以減少單個鏈接,但鏈接更長。
如果您的清單是1,000,000項,那麼您的差距應該是1,000。
您的漸近複雜度從單個鏈接列表的O(n)到此固定的第二級別的O(sqrt(n))。只有兩個級別,這是最好的選擇。
+0
這是一個完美的解釋。謝謝! – moo
相關問題
- 1. 找到特定間隔列表的最大值的最快方法
- 2. 陣列具有固定間隔大小
- 3. 在跳轉搜索中如何找到跳塊大小的最佳值?
- 4. 數組列表 - 級別的大小?
- 5. 查找日期列表中最大的時間間隔
- 6. 找到兩個表格的最大值,
- 7. 給定一個區間,找到所有的間隔在間隔
- 8. 通過跳過的級別確定圖像伽馬
- 9. 最佳的隔離級別爲特定應用
- 10. 查找列表上的最大數的兩個子句定義
- 11. 查找表的最小和最大值在一定的時間
- 12. 找到兩個列表的索引明智的最大值
- 13. 從一個列表中確定最大和最小x和y
- 14. 找到兩個整數之間的最大增量在列表中的蟒蛇
- 15. 重複對象的時間序列功能,並找到最佳時間間隔
- 16. 如何確定給定範圍內的最佳間隔數?
- 17. 如何找到兩個詞典列表之間的區別?
- 18. 如何找到兩個整數類型的最大(大小)?
- 19. 算法找到最佳的時間表
- 20. 找到[最大值,最小值在列表蟒列表值
- 21. 找到無衝突子集的確定性最佳選擇
- 22. 確定所有CSV列的最小值和最大值
- 23. 爲JBoss指定最佳的最小和最大堆大小
- 24. Highmaps最小和最大縮放級別
- 25. 比較兩個非常大的列表的最佳方法
- 26. 用於插入和查找的最佳散列表只有
- 27. 找到最大化另一個屬性的正確屬性
- 28. 如何找到鏈接列表的最大/最小元素
- 29. 將某個項目列表分組到特定最大大小的組中的最佳Python成語是什麼?
- 30. 找到給定值間隔的每個點的最小值(請參閱正文)
[Two Egg problem confusion]的可能重複(https://stackoverflow.com/questions/4171966/two-egg-problem-confusion) – Paul