時間複雜度和幅度提高訂單

Question

我有以下問題：

1. 對於下面的代碼，以理，給函數的時間複雜度。

2. 編寫一個執行相同任務但是在時間複雜度上有數量級提高的函數。具有更大（時間或空間）複雜性的功能將不會獲得功勞。

代碼：

int something(int[] a) { 
    for (int i = 0; i < n; i++) 
     if (a[i] % 2 == 0) { 
      temp = a[i]; 
      for(int j = i; j > 0; j--) 
       a[j] = a[j-1]; 
      a[0] = temp; 
     } 
} 

我在想，既然在最壞的情況下，temp = a[i]分配完成n倍，n時間複雜度被分配到這一點，a[j] = a[j-1]運行n(n+1)/2倍因此將時間複雜度值(n2+n)/2分配給該值，將它們相加返回時間複雜度爲n+0.5n2+0.5n，刪除常量將導致2n+n2和複雜度爲n2。

對於級的改進的順序：

int something(int[] a) { 
    String answer = ""; 
    for (int i = 0; i < n; i++) { 
     if (a[i] % 2 == 0) answer = a[i] + answer; 
     else answer = answer + a[i]; 
    } 
    for (int i = 0; i < n; i++) 
     a[i] = answer.charAt(i); 
} 

for循環被執行n倍，在第二for循環n倍第一內的代碼，求和給出了一個2n時間複雜度的數字。

這是正確的嗎？或者我做錯了什麼？

Answer 1

我想你的功能是安排一個列表的所有偶數列表的開頭，然後是奇數。

對於第一個功能，複雜度爲O（n ）如您所指定。

但是對於第二個函數，複雜度爲O（n）如果用於追加的運算符+是作爲恆定時間操作實現的。通常追加運算符+是作爲一個常量時間操作實現的，沒有任何隱藏的複雜性。所以我們可以得出結論：第二個操作需要O（n）時間。