你如何确定这个算法的平均情况复杂度？

Question

你如何确定这个算法的平均情况复杂度？

6

通常来说，计算最好情况和最坏情况的时间复杂度很容易，但是当涉及到平均情况，特别是给定概率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）; 我们如何推导出该算法的平均情况时间复杂度？

- lyming90

你是否假设如果存在零，则它们均匀分布在数组中？ - pjs

推导取决于您选择的“平均情况复杂度”的定义。它可以是“从某种规定的方式中随机选择数据的运行时间。” 这里可能是使用均匀分布选择每个矩阵元素，例如。或者它可能意味着“在每个可能的输入值上操作的总运行时间除以这些值的数量。” 在您的特定情况下，无论您选择哪种定义，它都将取决于int域的大小。 - Gene

@pjs 我认为它并没有假设那样。它只是说对于每个元素（i，j），有p的概率为零，因此有（1-p）的概率为非零。 - lyming90

那个公式对我来说真的没有多少意义。如果没有任何零，算法将遍历所有元素。但是，如果有零，问题就在于你要多久才能踩到第一个零，每次迭代概率都会增加，因为你在不重复地抽取观察值。如果零是逐渐减少的元素固定子集，谈论固定的p值就没有意义了。正确的模型应该是负超几何分布。 - pjs

@pjs 无论如何，是否有可能使用一系列m、n和p来表达平均比较？ - lyming90

我想我没有表达清楚。在你的描述中，“p”的概念是模糊不清的。很明显，没有一个有意义的“p”。因此，将平均比较描述为“p”的函数同样是含糊不清的。 - pjs

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

让我们考虑一个相关的问题。想象一下你有一枚硬币，正面朝上的概率为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从k=1到无穷大的和(k(1 - p)^k)。

我们不打算解决特定的求和，而是让它更加普遍化。让x成为某个变量，稍后我们将把它设置为1 - p，但现在我们将其视为自由值。然后，我们可以将上述求和重写为： p从k=1到无穷大的和(kx^(k-1))。

现在有一个巧妙的技巧：注意到这个表达式的内部是关于x^k关于x的导数。因此，这个和是： p从k=1到无穷大的和(d/dx x^k)。

导数是线性算子，所以我们可以将它移到前面： p d/dx从k=1到无穷大的和(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正面朝上，并且如果它们中的任何一个正面朝上，则停止。显然，您需要投掷的期望硬币数不会超过允许无限翻转的情况，因此您的期望运行时间最多为O(1 / p)（假设p > 0）。

如果我们假设p与m和n独立，则可以注意到，在一些初始增长之后，随着翻转次数的增加，每个被添加到总和中的项都比前面的指数级别较低。更具体地说，在将大约对数项添加到总和中之后，我们将与无限求和的情况相差甚远。因此，只要mn大致大于Θ(log p)，总和最终为Θ(1 / p)。因此从大O意义上讲，如果mn与p独立，则运行时间为Θ(1 / p)。