小编lym*_*g90的帖子

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