java - 依赖于抛硬币的 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 = ⌈log2(n)⌉ ( n) 以二为底的对数的上限。

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

乍一看，我认为预计时间复杂度为 O(log(log(n)))。我向我的助教提出了这个问题，在与他们讨论后，我们倾向于 O(1) 的平均运行时间，因为我们很可能只迭代一次或根本不迭代(例如 50%)。

Answer 1

当你有概率时，计算复杂度通常会很复杂。但你是对的，它是 O(1)，但不完全是 O(1)。 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