algorithm - 每次运行相同输入后，跳过列表的执行时间是否不同？

Question

我知道这个问题很简单，但我很想了解跳跃列表算法对执行时间的实际影响，该算法是随机算法对执行时间的影响。

它们在每次运行时都不同吗？

如果它们是，这是为什么该算法是随机的原因之一？

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

Answer 1

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

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

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

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

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

   现在，最低级别将是整个排序的链表。但是，下一个级别是在抛硬币（随机）的帮助下确定的。

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

但整体时间复杂度（摊销）保持不变。

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