依赖于硬币翻转的while循环的预期运行时间是多少

Question

我一直在为我的CS2类开发Java中的SkipList实现，在分析了我所有方法的运行时(为了好玩(后，我在确定以下方法的平均运行时时遇到了问题：

// Returns 1 with 50% probability, 2 with 25% probability,
// 3 with 12.5% probability, and so on, without exceeding maxHeight
private static int generateRandomHeight(int maxHeight)
{
int height = 1;
// At most O(maxHeight) which is O(log(n))
// Best case is O(1) and on average O(log(log(n)))??
while (--maxHeight > 0 && Math.random() < .5)
height++;
return height;
}

我知道最好的运行时是O(1(，最差的运行时间是O(h(，它保证是O(log(n((，因为h=₂(n( Ş(n的二个对数基底的天花板(。

问题是，此函数的平均预期运行时间是多少？

乍一看，我假设它应该是O(log(log(n(((。我向我的TA提出了这个问题，在与他们讨论后，我们倾向于O(1(的平均运行时间，因为我们很可能只迭代一次或根本不迭代(例如50%(。

Answer 1

当你有概率时，计算复杂性通常是复杂的。但你是对的，它是O(1(，但不完全是O(2(。O(1(被定义为常量，这意味着无论您输入什么，运行时间都是相同的。然而，在您的情况下，Math.random()是不可预测的。但是，尽管如此，它仍然是O(1(，因为随着n的增加，运行时间保持相对恒定。我做了一个测试来查看循环迭代的次数，结果非常相似。

public static void main(String[] args) {
List<Integer> l = new ArrayList<>();
for(int n = 0; n < 100; n ++) {
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < n; j++) {
if (Math.random() < 0.5) {
l.add(j);
break;
}
}
}
System.out.println(average(l));
l.clear();
}

}
private static double average(List<Integer> l) {
double sum = 0;
for(int i : l) {
sum += i;
}
return sum / l.size();
}

以下是一些结果。正如你所看到的，它们在1附近徘徊。

1.011
0.986
1.046
0.991
0.953
0.984
1.017
0.973