这些函数的平均复杂度是多少？

Question

我不确定如何计算平均复杂度。

if (condition) {
    for (1 : n) {
        do stuff
    }
}

给定这个具有给定条件的函数，如果它的条件在 99.9999999999999% 的时间内为假，我该如何计算它的复杂性；错误的70%？ 50%？ 10%？ 0.00000001%

Answer 1

如果我们用p（和p > 0）表示你的条件的概率，并且do stuff是一个常数时间操作，那么你的算法的时间复杂度将是O(p*n) = O(n).

在这种情况下，您选择的概率对时间复杂度没有影响这一事实可能确实会引起一些混淆。自然地，如果 p = 0.5，该算法平均会运行一半的时间就好像 p=1。但是 big-O 是函数增长的速率的度量，这就是常数项没有影响的原因。

然而，平均时间复杂度可能比这更有趣。尤其是当概率取决于输入时，很容易构造一个发生有趣事情的例子。考虑以下算法：

r = a uniformly random integer from 1 to n
if (r==1) {
    for (1 : n) {
        do stuff
    }
}

现在，foor 循环将以 1/n 的概率执行，因此平均时间复杂度将为 O(1/n * n) = O(1)。请注意，最坏情况下的时间复杂度仍然是 O(n).

有关更实际的示例，请考虑 Quicksort algorithm。它的平均时间复杂度为 O(n*log(n))，而最坏情况下的时间复杂度为 O(n^2)。这里影响概率的是输入列表中的元素，而不是它的长度 n.

What's the average complexity of these functions?