随机搜索算法的复杂性

Question

在排序a的长度数组上考虑以下随机搜索算法n(按递增顺序).x可以是数组的任何元素.

size_t randomized_search(value_t a[], size_t n, value_t x)
    size_t l = 0;
    size_t r = n - 1;
    while (true) {
        size_t j = rand_between(l, r);
        if (a[j] == x) return j;
        if (a[j] < x) l = j + 1;
        if (a[j] > x) r = j - 1;
    }
}

当从中随机选择时,该函数的Big Theta复杂度(下面和上面都有)的期望值x是a多少？

虽然这似乎是log(n),但我进行了一个指令计数实验,发现结果增长的速度比log(n)(根据我的数据,甚至(log(n))^1.1更适合结果)快一点.

有人告诉我,这个算法有一个确切的大theta复杂性(所以显然log(n)^1.1不是答案).那么,您能否将时间复杂性与您的方法一起证明呢？谢谢.

---

更新:我的实验数据

log(n) 适合mathematica的结果:

log(n)^1.1 拟合结果:

Answer 1

如果您愿意切换到计算三向比较,我可以告诉您确切的复杂性.

假设密钥位于位置i,我想知道与位置j的预期比较数.我声称,当且仅当它是i和j之间的第一个位置进行检查时,才检查位置j.由于每次都是随机均匀地选择枢轴元素,因此概率为1 /(| i - j | + 1).

总复杂度是对sum_ {j = 1} ^ n 1 /(| i - j | + 1)的i < - {1,...,n}的期望,这是

  sum_{i=1}^n 1/n sum_{j=1}^n 1/(|i - j| + 1)
= 1/n sum_{i=1}^n (sum_{j=1}^i 1/(i - j + 1) + sum_{j=i+1}^n 1/(j - i + 1))
= 1/n sum_{i=1}^n (H(i) + H(n + 1 - i) - 1)
= 1/n sum_{i=1}^n H(i) + 1/n sum_{i=1}^n H(n + 1 - i) - 1
= 1/n sum_{i=1}^n H(i) + 1/n sum_{k=1}^n H(k) - 1  (k = n + 1 - i)
= 2 H(n + 1) - 3 + 2 H(n + 1)/n - 2/n
= 2 H(n + 1) - 3 + O(log n / n)
= 2 log n + O(1)
= Theta(log n).

(log表示自然日志.)请注意低位项中的-3.这使得看起来比较的数量在开始时比对数增长得快,但是渐近行为表明它会趋于平稳.尝试排除小n并重新设置曲线.