二次时间算法

def prefix_avg(list1):
  n = len(list1)
  avg = n * [0]
  for i in range(n):
    total = 0
    for j in range(i+1);
      total += list1[j]
    avg[i] = total/(i+1)
  return avg

total = sum(list1[0:i+1])       # 不用第二次遍历

i从0到n-1，运行了n次，所以外层的时间复杂度是O(n) , 里面的j的运行次数是1+2+3+...+n , 总的次数是 (1+n)n/2 ,时间复杂度是O(nn) , 所以总的时间复杂度是O(n*n)
sum() 直接求列表和的方法