算法是这样的:
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是data中元素的个数)。
关于algorithm - Knuth 方差算法的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25997873/