math - 有序循环链表中随机整数的存在性

Question

这是我的任务:

存在一个有 n 个整数的循环有序链表。每个元素都有一个指向下一个更大项目的后继指针。列表中最大的项目指向最小的项目。确定传入的目标项是否是列表的成员。您可以通过两种方式访问​​列表中的项目:您可以跟随已访问项目的下一个指针，或者可以使用函数“RAND”，该函数返回指向列表中均匀随机项目的指针。创建一个随机算法，找到目标项，最多进行 O(√n) 次期望传递，并始终返回正确的答案。

我不确定如何以所需的时间复杂度构建算法。我认为这与计算和存储列表中的一些总和有关，但无法弄清楚这一步。

Answer 1

解决方案基于戴夫的评论:

Use RAND sqrt(n) times, storing the largest element < target. Show that this is expected to be within sqrt(n) of the target.

用i表示列表中小于目标元素的最大元素的索引。

现在让我们计算在 sqrt(n) 试验中击中 (i - sqrt(n), i] 范围内的元素的期望。在每次试验中，概率命中范围是范围长度除以列表长度，即 sqrt(n)/n = 1/sqrt(n)，所以

E = 1/sqrt(n) * sqrt(n) = 1.

因此，我们希望通过在 sqrt(n) 试验中选择小于目标的最大元素来检查目标元素是否存在，然后线性推进 sqrt(n) 项目。