找到只有兩個級別的確定性跳過列表的最佳間隔大小

Question

我試圖製作一個具有隻有兩個級別的恆定間隙大小的「完美」跳過列表。從計算不同大小的跳過列表的訪問節點，我可以看出它是由大小決定的，但我無法用n來計算公式。

Answer 1

如果您確實需要恆定的間隙大小，那麼您的最佳間隙大小就是列表長度的平方根。例如，如果您的跳過列表長度爲16個項目，則最佳間隔大小爲4.要到達第15個項目，您需要進行3次長跳躍和3次短跳躍。這是最糟糕的情況。

要得到第k個項目，你關注了k/sqrt(n) + k%sqrt(n)鏈接。

更大的間隙大小會讓你更快地結束，但爲了獲得列表中的某個位置，你可能必須遵循更多的單一鏈接。平均而言，您將遵循更多鏈接。如果間隙較小，則可以減少單個鏈接，但鏈接更長。

如果您的清單是1,000,000項，那麼您的差距應該是1,000。

您的漸近複雜度從單個鏈接列表的O（n）到此固定的第二級別的O（sqrt（n））。只有兩個級別，這是最好的選擇。