for循環內的一個while循環 - o（n）平方？

Question

我正在比較bubblesort的實現，並在「while」循環中看到了一個帶for循環的替代方案。已知泡泡排序是o（n^2）。如果在while循環中使用for循環，它仍然如此嗎？我想了一會兒，一時間複雜if語句是相同的（即線性）：

Array.prototype.bubblesort = function() { 
    var done = false; 
    while (! done) { 
    done = true; 
    for (var i = 1; i < this.length; i++) { 
     if (this[i - 1] > this[i]) { 
     done = false; 
     var tmp = this[i - 1]; 
     this[i - 1] = this[i]; 
     this[i] = tmp; 
     } 
    } 
    } 
    return this; 
} 

Answer 1

一個循環的時間複雜度取決於所執行的迭代次數，以及個人循環的複雜性身體。迭代次數取決於循環退出條件，它本身可能取決於循環體中發生了什麼。

您可以從最裏面的循環到最外面的循環執行分析。

在這種情況下，內部循環（for）總是執行length次，並且主體執行有限數量的操作。因此內循環的複雜性是O(length)。

對外部循環（while）的討論稍微複雜一些，因爲它取決於內部循環設置的done標誌。所以外層循環的迭代次數是可變的，取決於數組的內容。如果沒有更深入的研究，我們可以說，會有外環的至少一次迭代，最多length迭代。內部循環是這樣的，它移動最大元素到最右邊的位置，則第二大到前-最右邊的位置，依此類推：

後者的陳述可以如下理由。無論初始配置如何，在經過length後，不會再出現掉期。

總之，我們可以肯定算法在最壞的情況下需要時間O(length²)，最好的情況是O(length)，即當數組最初排序時。