algorithm - 顺序搜索时间中的预期搜索时间

Question

我有一个按概率降序排列的项目列表。分布遵循 zipf's，即 key i 的相对概率为 1/i。在这些情况下，顺序搜索的大 O 预期搜索时间是多少。

Answer 1

预期的搜索时间是:

第 i 个元素的概率乘以找到第 i 个元素所需的工作。

对于相对概率，这是:1 * 1 + 1/2 * 2 + 1/3 * 3 + ... = N

要得到结果，你必须对其进行归一化，也就是说，你必须将其除以相对概率的总和:1 + 1/2 + 1/3 + ...，这是 N 次谐波数，大约 log N。

所以答案是 O(N/log N)。