如何计算Java PrefixAverages算法

Question

那里我有这两个算法是从伪代码实现的。我的问题是，如何计算基本操作并为两种算法导出T（n），并找出每种算法的（Big-Oh，O（n））的时间复杂度？

public class PrefixAverages1 { 

static double array[] = new double[10]; 

public static void prefixAverages(){ 

for (int i = 0; i < 10; i++){ 

    double s = array[i]; 

     for (int j = 0; j < 10; j++){ 

      s = s + array[j]; 
     } 

    array[i] = s/(i + 1); 

    System.out.println(Arrays.toString(array)); 
} 

} 
public static double[] prefixAverages(double[] inArray) { 
double[] outArray = new double[inArray.length]; 
return outArray; 

} 


public static void main(String... args) { 
System.out.println(
    Arrays.equals(
     prefixAverages(new double[] {5, 6, 7, 8}), 
     new double[] {2, 2.5, 3.5, 4} 
    ) 
); 
} 
} 

Prefix2

import java.util.Arrays; 

public class PrefixAverages2 { 

static double array[] = new double[10]; 

public static void prefixAverages(){ 

    double s = 0; 

    for (int i = 0; i < 10; i++){ 
      s = s + array[i]; 
      array[i] = s/(i + 1); 
    } 
     array[0] = 10; 

    System.out.println(Arrays.toString(array)); 
} 

public static double[] prefixAverages(double[] inArray) { 
double[] outArray = new double[inArray.length]; 
return outArray; 

} 


public static void main(String... args) { 
System.out.println(
    Arrays.equals(
     prefixAverages(new double[] {3, 4, 5, 6}), 
     new double[] {2, 3.5, 4, 5} 
    ) 
    ); 
} 

} 

Answer 1

首先，原始的操作被认为的款项（或减）和乘法（或部门），你必须在你的代码。你可以从你的伪代码中对它们进行计数。

所以，这意味着s = s + array[j];这个计为1这样的操作，也是这样的array[i] = s/(i + 1);。

大O（复杂度）基本上就是你的算法在元素数量和所需操作之间的关系。

以你为例，你有10个元素（如在new double[10];和i < 10部分），并要求算法1：10x（10 + 1）操作。

本作进行了分析：

• 你有10次
• 外环您有还10次内部循环（这不可能是不同的，因为你不能得到的结果不同）这意味着外部和内部循环的数量在这个算法中是相同的，比如说'N = 10'
• 您在每个运行的外部循环中也有一个分区，所以您在这里有+1操作。

所以，10(outer)x(10(inner)+1(division)) = 110

要获得的复杂性，认为： 如果您双击如何原始操作的数量受影响的元素的数量？ 让我们看看： Complexity(N) = Nx(N+1) so Complexity(2N) = (2N)x((2N)+1) = 4N^2 + 2N。

但是因为在复杂性方面，真正重要的是我们得到的最大程度： Complexity(2N) ~ 4N^2。此外，我们最终得到的程度之前的固定因子无关： Complexity(2N) ~ N^2这意味着您的第一个算法是O(N^2)。

你可以为你的下一个算法做数学运算。

P.S.分母操作不算一个：(i + 1)。

P.S.2它不是一个SO问题，但它不是编程的问题。