algorithm - 您如何确定该算法的平均情况复杂度？

Question

通常很容易计算最好情况和最坏情况的时间复杂度，但是当涉及到平均情况，尤其是给定概率 p 时，我不知道从哪里开始。

让我们看看下面的算法来计算矩阵中所有元素的乘积:

int computeProduct(int[][] A, int m, int n) {
    int product = 1;
    for (int i = 0; i < m; i++ {
        for (int j = 0; j < n; j++) {
            if (A[i][j] == 0) return 0;
            product = product * A[i][j];
        }
    }
    return product;
}

假设 p 是 A[i][j] 为 0 的概率(即算法终止于此，返回 0)；我们如何得出该算法的平均用例时间复杂度？

Answer 1

让我们考虑一个相关的问题。假设您有一枚硬币，正面朝上的概率为 p。按照预期，您需要抛多少次硬币才能正面朝上？答案是 1/p，因为

• 您有 p 的机会需要翻转一次。
• 您有 p(1-p) 次机会需要抛两次(第一次必须朝反面，第二次必须朝正面)。
• 您有 p(1-p)^2 次机会需要翻转三次(前两次翻转需要出现反面，第三次需要出现正面)
• ...
• 有 p(1-p)^(k-1) 次机会您需要进行 k 次翻转(前 k-1 次翻转需要出现反面，第 k 次需要出现正面。)

所以这意味着翻转次数的期望值是

p + 2p(1 - p) + 3p(1 - p)^2 + 4p(1 - p)^3 + ...

= p(1(1 - p)^0 + 2(1 - p)^1 + 3(1 - p)^2 + ...)

所以现在我们需要算出这个总和是多少。一般形式为

p sum from k = 1 to infinity (k(1 - p)^k).

与其求解这个特定的求和，不如让它更通用。假设 x 是某个变量，稍后我们将其设置为 1 - p，但现在我们将其视为一个自由值。那么我们可以将上面的求和重写为

p sum from k = 1 to infinity (kx^(k-1)).

现在有一个可爱的把戏:注意这个表达式的内部是 x^k 对 x 的导数。因此，这笔款项是

p sum from k = 1 to infinity (d/dx x^k).

导数是一个线性算子，所以我们可以把它移到最前面:

p d/dx sum from k = 1 to infinity (x^k)

内和 (x + x^2 + x^3 + ...) 是 1/(1 - x) - 1 的泰勒级数，因此我们可以将其简化为

p d/dx (1 / (1 - x) - 1)

= p / (1 - x)^2

因为我们选择了 x = 1 - p，这简化为

p / (1 - (1 - p))^2

= p / p^2

= 1 / p

哇!那是一个很长的推导。但它表明所需的预期抛硬币次数为 1/p。

现在，在您的情况下，您的算法可以被认为是抛出 mn 个硬币，正面朝上的概率为 p，如果其中任何一个正面朝上则停止。当然，您需要 throw 的预期硬币数量不会超过允许您无限次翻转的情况，因此您的预期运行时间最多为 O(1/p)(假设 p > 0) .

如果我们假设 p 独立于 m 和 n，那么我们可以注意到在一些初始增长之后，随着翻转次数的增加，每个添加到我们求和中的项都比之前的项呈指数级下降。更具体地说，在将大致对数的许多项添加到总和后，我们将偏离无限总和的总数。因此，假设 mn 大致大于 Θ(log p)，则总和最终为 Θ(1/p)。所以在 big-O 意义上，如果 mn 独立于 p，则运行时间为 Θ(1/p)。