Java 数组建议

Question

我正在做一道练习题，但遇到了困难。问题是

“给定一个包含 n 个数字(例如 double )的数组 a，考虑计算问题前 i 个数字的平均值，对于 i范围从 0至n-1 。也就是说，计算长度为 n 的数组 b ， 在哪里 b[i] = a[0] + a[1] ....+ a[i]/(i + 1)对于 0 <= i < n 。编写一个Java程序来解决这个问题。您的程序可以生成自己的数组，例如a[i] = i + 1 。看看您可以在不到5秒。 (要获得全额学分，至少应为一百万。)描述算法的时间复杂度。”

这是我解决这个问题的尝试:

public class largeArray{

public static void main(String[] args){

  double[] aa = new double[1000000];
  System.out.println(CalculateAvg(aa));




}
public static double CalculateAvg(double[] a){
  int i =0;
  double[] array = new double[i];
  a[i] = i + 1;

  for(int k=0; k<array.length; i++){
     double total = a[k]+a[k];
     double sum = ((total)/a[i]);
  }

 return a[i];
 }
}

Answer 1

如果我猜对了，你必须生成一个数组 B，其中 B[i] 是输入数组的前 i 个元素的平均值。

如果这是问题所在，您可以创建一个循环，对 A[i] + B[i-1] 求和，然后执行 B[i-1]/i；

如果 A 是输入数组，B 是输出，则应该是这样:

B[0] = A[0]
for (int i = 1; i < n; i ++) {
    B[i] = A[i] + B[i-1];
    B[i-1] /= i;
}
B[n-1] /= n;

这是 O(n)，就复杂度而言是最佳的(因为问题是计算 n 个数的平均值为 T(n)，即不能用小于 O(n) 的复杂度来解决)。

而且这个常数非常低，因为每个循环只有几条指令。这应该会让你的时间低于 5 秒。

啊我忘了，A的生成是在5秒分析之外的(它是输入)。

问候