经典指数          
原因
2777
浏览数
0
收藏数
 

对于移动平均算法,是计算某变量之前n个数值的算术平均,正确的说法是:
  • 空间复杂度是O(l)
  • 空间复杂度是O(n)
  • 空间复杂度是O(logn)
  • 空间复杂度是O(nlogn)

     举报   纠错  
 
切换
1 个答案

 任何一个算法不同情况下可能有多种解法,一般我们以时间复杂度为评判的话,就会用牺牲空间换时间。

这个算法最明显的有两种解法,

1.每次进来一个变量n,就遍历前面n个数,然后求和,再取平均,这样的话时间复杂度为O(n),空间为O(1);

2.以空间换时间:从前往后没计算一次保留一次求和值到一个辅助空间,这样计算下一个的时候直接取得前一个和值加上当前数,再取平均得到当前平均,这样的话时间复杂度为O(1),空间为O(n) 

 
切换
撰写答案