嵌套循環運行時間複雜度分析

我得到低於插入排序算法，它包括嵌套的for循環：嵌套循環運行時間複雜度分析

public InsertionSort(AnyType [] a){ 
    int m; 
    for(int n = 1; n < a.length; n++){ 
     AnyType temp = a[n]; 
     for(m = n; m > 0 && tmp.compareTo(a[ m - 1]) <= 0; m--) 
      a[ m ] = a[ m - 1 ]; 
     a[ m ] = temp; 
    } 
}

第一環路已運行時間爲O（N），第二個是O（N^2 ），所以嵌套循環中的總運行時間應該是O（N * N^2 = N^3），對嗎？但是我知道在插入排序中最壞的情況應該是O（N^2），但是我的老師改變了這段代碼，通過替換[m-1]）< = 0來代替使用一個[m - 1]）< 0.所以我很困惑，我怎麼來計算比最壞的情況更糟糕的情況。有人幫忙嗎？提前致謝。

來源

2016-11-11 Student

第二個循環看起來也'O（N）'對我來說，這將得到所需要的'O（N^2）'用於插入排序的整體性能。 –

但是，如果我嘗試對具有所有相同元素的數組進行排序，那麼比較和交換的次數都是1 + 2 + 3 + ... n-1次，直到排序結束，所以我得到n（n-1）/ 2 = O（n^2） – Student

這不是傳統的插入排序代碼，我的老師通過替換[m-1]）<= 0而不是使用[m-1]）<0 – Student

第二個是O（N^2）

這是不對的。怎麼看。

考慮a.length = N，TC應O(N^2)。

因爲(1 + 2 + 3 + ... + N-1) = N(N-1)/2 = O(N^2)

內循環運行1周時間比以前更多的時間。

[1, 1] 
[2, 1] 
[3, 1] 
... 
[N-1, 1]

來源

2016-11-11 03:54:29

我完全同意:-) –

對（INT n = 1時; N <則爲a.length; N ++）{

在該上面的行，則通過陣列去N - 1次（自你開始於索引1所有則爲a.length -1）的方式，從而O（N）

對（M = N; M> 0 & & tmp.compareTo（a [m-1]）< = 0; M--）

在該內環，你開始以n，然後向下移動，因此，在最壞的情況下，你將被從當前值Ñ一路下降到1，從而執行多達n次比較。

因此，我們可以看到在最壞的情況下：

第一次迭代：你是從1將1
第二次迭代：你是從2將1
第三次迭代：你是從3將1
...
第N-1次迭代：要從Ñ去-1到1

因此，要執行1 + 2 + 3 + 4 + ...N - 總共1個操作它等於：

（N）（N-1）/ 2 = O（N^2）

來源

2016-11-11 04:49:40 cullan

讓我們的代碼像下面簡單。

public InsertionSort(AnyType [] a){ 
    // A value n 
    for(; n < length ;){ 
     // A value m 
     for(; m < someLength ;) { 
      // do something. 
     } 
    } 
}

正如您所說，'someLength'可以從n-1開始。

但讓我們看看內部循環方面的代碼。

blahblah 
     for(; m < someLength ;) { 
      // do something. 
     } 
    blahblah

它運行只someLength - 米（或無如果它是下0）倍

，其是直

，其被表示爲N（爲O（N））。

還有一件事。

1 + 2 + 3 + 4 + ... + n-1個不能沒有外循環中發生，可以嗎？

那麼你爲什麼要計算內環的複雜性呢？

來源

2016-11-11 05:14:24

嵌套循環運行時間複雜度分析

回答

相關問題