找到只有两个级别的确定性跳过列表的最佳间隔大小

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））。只有两个级别，这是最好的选择。