关于跳过列表元素频率

Question

首先，我不太了解跳表，我只是想为我的考试做准备。当跳过列表中有log(n)列表时，每个级别上用于最佳搜索(log(n))的元素的频率是多少？我知道当使用2个列表时，第一个列表有n个元素，第二个列表有sqrt(n)元素。因此，在搜索元素时，我在第二个列表(上面的列表)上执行最多的sqrt(n)步骤，在第一个列表(包含所有元素的那个列表)中执行sqrt(n)步骤，因为元素之间的间隙是sqrt(n)-long。所以这看起来没问题。但是当使用log(n)列表时，每个列表有多少个元素呢？

Answer 1

当一个元素被添加到跳跃列表中时，“一枚硬币被抛出”几次来决定新元素应该包括在多少层。每次硬币正面着地时，元素总是被添加到第一(最低)层，然后添加到下一层。如果我们将掷硬币中获得正面的概率称为p(通常使用p= 0.5 )，则每个元素以概率1添加到第一层，以概率p添加到第二层，以概率p^2添加到第三层，并且通常以概率p^(i-1)添加到第i层。如果跳过列表包含n个元素，则第二层包含期望中的n*p个元素(不是sqrt(n))，第三层包含n*p^2个元素，通常是第i层n*p^(i-1)个元素。例如，在p= 0.5和n= 64个元素的跳跃列表中，我们预计第二层包含大约32个元素，第三层大约包含16个元素，依此类推，因此我们希望总共有大约log_(1/p)(n) = log_2(n)层。要在跳过列表中搜索元素，我们首先线性扫描最上面的列表(它只包含几个元素，可能是2个或3个)。这允许我们将搜索范围限制在下面列表中的较小范围内。然后我们扫描下面列表的范围，重复这个过程，直到我们到达最底部的列表。当p= 0.5时，您几乎可以将其视为二进制搜索。例如，对于n= 64个元素，我们期望在最上面的列表中采取大约32个元素的大约2个步骤，将我们在下面列表中的搜索限制在大约32个元素的范围内。然后我们将以大约16个元素的步长扫描下面列表中的这32个元素，依此类推。