7

考虑以下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 复杂度（上下都有界）的期望值是多少？xa

虽然看起来是这样log(n)，但我做了一个指令计数的实验，发现结果增长速度比log(n)（根据我的数据，甚至(log(n))^1.1更好地拟合结果）。

有人告诉我，这个算法有一个非常大的 theta 复杂度（所以显然log(n)^1.1不是答案）。那么，您能否给出时间复杂度以及您的证明方法？谢谢。

更新：我的实验数据

log(n)数学拟合结果：

日志（n）

log(n)^1.1拟合结果：

日志(n)^1.1

4

2 回答 2

5

如果您愿意改用计算三向比较，我可以告诉您确切的复杂性。

假设密钥在位置 i，我想知道与位置 j 比较的预期次数。我声称位置 j 被检查当且仅当它是 i 和 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 并重新拟合曲线。

于 2013-05-22T15:30:30.943 回答
2

假设rand_between在恒定时间内从均匀概率分布中实现采样，该算法的预期运行时间为 Θ(lg n )。证明的非正式草图： 的期望值rand_between(l, r)是(l+r)/2，它们之间的中点。所以每次迭代都应该跳过数组的一半（假设大小是 2 的幂），就像二进制搜索的单次迭代一样。

更正式地说，借用对quickselect的分析，观察到当你选择一个随机中点时，一半的时间它将在 ¼ n和 ¾ n之间。左子数组和右子数组都没有超过 ¾ n 个元素。另一半时间，两者都没有超过n 个元素（显然）。这导致递归关系

T(n) = ½T(¾n) + ½T(n) + f(n)

其中 f( n ) 是每次迭代的工作量。两边减去½T(n)，然后两边加倍，我们有

½T(n) = ½T(¾n) + f(n)
T(n) = T(¾n) + 2f(n)

现在，由于 2f( n ) = Θ(1) = Θ( n ᶜ log⁰ n ) 其中c = log(1) = 0，因此由主定理 T(n) = Θ( n ⁰ lg n ) = Θ(lg n )。

于 2013-05-22T15:04:23.837 回答