algorithm - 方差的渐近运行时间是多少？

如你所见，我对所有这些运行时分析还很陌生，我想确保我计算的每一步都是正确的。。
我也不喜欢用伪代码的形式写，所以我用Python来代替来了

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

因此，平均值的总运行时间（如果im错误，请更正me）=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

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

最佳答案

o（n^2），因为您正在执行o（n）操作n次。
一般来说，在确定运行时，循环是乘法的；如果方差循环是“for i i n 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），但是分析有点棘手：您需要取arithmetic series“1+2+3+的和…+n-1+n“，即n*（n-1）/2，或O（n^2）

关于algorithm - 方差的渐近运行时间是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17381080/