如何計算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問題，但它不是編程的問題。