algorithm - Knuth方差算法的复杂性

算法如下：

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），但似乎太简单了。我遗漏了什么吗或许也应该考虑到分歧？

最佳答案

你是对的，复杂性是O（n）。for循环中的语句以恒定时间执行，并执行n次（其中n是数据中的元素数）。

关于algorithm - Knuth方差算法的复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25997873/