0

我正在做一个练习题，我被卡住了。问题是

“给定一个包含 n 个数字的数组 a（比如双精度数），考虑计算前 i 个数字的平均值的问题，i范围从0到n-1。也就是说，计算长度为 的数组 b n，其中 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];
 }
}
4

2 回答 2

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秒分析之外（它是输入）。

问候

于 2013-09-25T21:58:32.427 回答
0

开始制作一个函数来获取 n 个给定数字的平均值 ( maxNum)

public int getAvgForNumbers(int maxNum){
int sum = 0;

for(int k=1; k<=maxNum; k++){
     sum = sum + k;
  }

return sum/maxNum;
}

现在使用这个函数来填充你的数组，从值 1 开始调用它 -getAvgForNumbers(1)直到你觉得会得到一个数字getAvgForNumbers(x)

于 2013-09-25T21:46:20.593 回答