0

正如你所看到的，我对所有这些运行时分析仍然很陌生，并且想确保我计算的每一步都是正确的。我也讨厌用伪代码形式编写，所以我用 Python 来代替。

def mean(n):
    sum = 0               #cost = 1
    for i in n:           #cost = n
        sum += i          #cost = n
    return sum/len(n)     #cost = 1

因此，平均值的总体运行时间（如果我错了，请纠正我）= O(1) + O(n) + O(n) + O(1) = O(n)

def variance(n):
    var = 0                    #cost = 1
    for i in n:                #cost = n
        var += (i-mean(n))**2  #cost = n*n or n+n ??
    return var / len(n)        #cost = 1

问题是方差的总体运行时间是多少？你能展示所有的工作吗？

4

1 回答 1

1

O(N^2)，因为您正在执行 N 次 O(N) 操作。

一般来说，循环在确定运行时是乘法的；如果您的方差循环是“for i in lg(n)”，那么您的运行时间将为 O(N * lg(N))，因为您将执行 O(N) 操作 lg(N) 次；同样，如果您的内部操作为 O(2^N)，外部循环为“for i in n”，那么您的运行时间将为 O(N * 2^N)

另一种常见的循环格式是

for(int i = 0; i < N; i++) {
    for(int j = i; j < N; j++) {
        // O(1) operation
    }
}

这仍然是 O(N^2)，但分析有点棘手：您需要取算术级数“1 + 2 + 3 + ... + n-1 + n”的总和，即 n * ( n - 1) / 2，或 O(N^2)

于 2013-06-29T14:20:34.050 回答