algorithm - Knuth 方差算法的复杂性

Question

算法是这样的:

def online_variance(data):
    n = 0
    mean = 0
    M2 = 0

    for x in data:
        n = n + 1
        delta = x - mean
        mean = mean + delta/n
        M2 = M2 + delta*(x - mean)

    if (n < 2):
        return 0

    variance = M2/(n - 1)
    return variance

取自Wikipedia .

问题是这个算法的时间复杂度是多少？我的答案是 O(N)，但这似乎太简单了。我错过了什么吗？也许还应该考虑这些部门？

Answer 1

你是对的，复杂度是 O(n)。 for循环中的语句以恒定时间执行，执行n次(其中n是data中元素的个数)。