对于相同的输入，每次运行后Skip list的执行时间是否不同？

Question

我知道这个问题很微不足道，但我很想知道跳表算法对执行时间的实际影响是什么。

他们每次跑步都是不同的吗？

如果是，这是这个算法被随机化的原因之一吗？

如果是，那么我们是否可以得出结论，随机化算法也将执行时间随机化？

Answer 1

因此，这里的主要问题是您希望在跳过列表上执行哪些操作。

假设你有一个现有的跳过列表，你只想搜索其中的几个元素。(

1. )假设你有一个现有的跳过列表，你只想搜索其中的一些元素。

搜索算法不是随机化的。虽然它取决于级别的总数，但建议将它们保持在O(log )以获得有效的性能。

因此，对于静态跳过列表，搜索执行时间是相同的。

1. 如果您有一组数字，并且想要创建跳过列表，然后执行某些操作

现在，最低级别将是整个排序的链表。然而，下一个级别是通过抛硬币(随机)来确定的。

在这里，不能保证构建的跳过列表在多次运行后是相同的。因此，搜索时间也会有所不同。

但总体时间复杂度(摊销)保持不变。

它被随机化的原因是为了处理性能。如果我们想一种静态的方式来创建级别，那么肯定会有影响时间复杂性的最坏情况的输入。即使在随机性的情况下，这也是可能的，但想法是它发生的概率非常小。这就是为什么随机算法是有效的。