算法的時間複雜度

我已經創建了兩個算法來計算給定數組的前綴平均值。我想要推導出這兩種算法的時間複雜性，但我一直在努力。我看過這個YouTube視頻： https://www.youtube.com/watch?v=udwxWq9wZgg&safe=active。我不明白如何計算for循環和嵌套for循環中的操作。算法的時間複雜度

在2:27，我設法計算了PrefixAverages2 for循環中的操作。這是3n + 1。但是，從5:50起我無法理解。

在此先感謝。

public double[] PrefixAverages1(double input[]) 
{ 
    double A[] = new double[input.length]; 
    double s; 


    for(int i=0; i <= input.length - 1 ;i++) 
    { 
     s = input[0]; 

     for(int j=1; j <= i ;j++) 
     { 
      s = s + input[j]; 
     } 

     A[i] = s/(i+1); 
    } 


    return A; 

} 





public double[] PrefixAverages2(double input[]) 
{ 
    double A[] = new double[input.length]; 
    double s = 0; 

    for(int i=0; i <= input.length - 1 ; i++) 
    { 
     s = s + input[i]; 
     A[i] = s/(i+1); 

    } 

    return A; 

}

來源

2015-10-15 Rob Neal

檢查這些問題，他們可能會幫助你：[第一]（http://stackoverflow.com/questions/487258/）/ [第二]（http://stackoverflow.com/questions/3255/）。 – Laf

而問題在哪裏？無論如何，第二個是微不足道的，前者只是總結從1到'input.length'的所有整數 - 關閉的公式爲n *（n + 1）/ 2 – Voo

因此計算第一個算法的運算： 1 + n *（n + 1）/ 2 + 2 + 1這就是n *（n + 1）/ 2 + 4 –

for(int i=0; i <= input.length - 1 ;i++) 
     for(int j=1; j <= i ;j++)

這是二次的，對於給定的我，內環轉到關於i-倍，所以你必須要總結過我，所以基本上你有什麼樣sum_ {i = 1}^{I = l} i，它是前l個整數的和，所以l（l + 1）/ 2，然後是二次的。

對於第二種算法，您只需要一個循環，因此它的複雜性是線性的。

來源

2015-10-15 19:43:25

第一行：3n + 1第二行：3n + 1 so 9N^2 + 2？ –

（第一個算法）您有：內循環中i = 0 - > 0次，內循環中i = 1 - > 1次，內循環中i = 2 - > 2次，內部循環中i = 3 - > 3次循環，所以0 + 1 + 2 + 3 ...直到長度-1 ...所以正好長度（長度-1）/ 2。在第二個算法中，您只需從0到長度爲1，因此長度乘以循環的內容即爲線性。您必須計算給定循環內容的執行次數...... –

算法的時間複雜度

回答

相關問題