嵌套在while循環中的for循環的時間複雜度是多少？

Question

我想優化一個函數。我相信這個嵌套for循環是二次的，但我不積極。我已經重新創建下面

const bucket = [["e","f"],[],["j"],[],["p","q"]] 
 
let totalLettersIWantBack = 4; 
 

 
//I'm starting at the end of the bucket 
 
function produceLetterArray(bucket, limit){ 
 
    let result = []; 
 
    let countOfLettersAccumulated = 0; 
 
    let i = bucket.length - 1; 
 
    while(i > 0){ 
 
     if(bucket[i].length > 0){ 
 
     bucket[i].forEach((letter) =>{ 
 
     if(countOfLettersAccumulated === totalLettersIWantBack){ 
 
      return; 
 
     } 
 
     result.push(letter); 
 
     countOfLettersAccumulated++; 
 
     }) 
 
     } 
 
     i--; 
 
    } 
 
    return result; 
 
} 
 

 
console.log(produceLetterArray(bucket, totalLettersIWantBack));

Answer 1

這裏是一個技巧對於這樣的問題。對於您要分析其複雜性的代碼，只需在假設沒有其他語句存在的情況下，在最壞的情況下寫出執行每條語句所需的時間。注意：評論與#operations worst case:

begining對於給定的代碼：

while(i > 0){ //#operations worst case: bucket.length 
    if(bucket[i].length > 0){ //#operations worst case:: 1 
    bucket[i].forEach((letter) =>{ //#operations worst case: max(len(bucket[i])) for all i 
    if(countOfLettersAccumulated === totalLettersIWantBack){ //#operations worst case:1 
     return; 
    } 
    result.push(letter); //#operations worst case:1 
    countOfLettersAccumulated++; //#operations worst case:1 
    }) 
    } 
    i--; ////#operations worst case:: 1 
} 

我們現在可以乘所有最壞情況下的時間（，因爲它們都可以在最壞的情況下實現的，你總是可以設置totalLettersIWantBack = 10^9），以獲得片斷的O複雜性：

複雜性= O(bucket.length * 1 * max(len(bucket[i])) * 1 * 1 * 1 * 1)

= O(bucket.length * max(len(bucket[i]))

如果每個桶[I]的長度是恆定的，K，那麼你的複雜性減少到： O(K * bucket.length) = O(bucket.length)

注意，按壓操作的複雜性可能不能保持爲恆定元素數量增長（最終，運行時將需要爲添加的元素分配空間，並且所有現有的元素可能不得不移動）。

Answer 2

此功能在技術上是其中n是總的元素個數在矩陣是線性的。這是因爲，退出條件是桶的長度和用於桶每個陣列你是否countOfLettersAccumulated等於totalLettersIWantBack。不斷觀察價值。

如果您正在尋找與您的矩陣尺寸匹配的答案，它會變得更加複雜，因爲它看起來像存儲桶的尺寸不固定。

您可以通過添加桶的foreach這要是countOfLettersAccumulated之外的附加檢查把這段代碼爲常數等於 totalLettersIWantBack然後你做一個突破。

Answer 3

這是否是二次方取決於您考慮的內容以及如何組織桶。如果N是字母總數，那麼運行時將受到桶中桶的數量的限制，如果N大於N，或者它受到桶中字母數量的約束，如果N較大。在任何一種情況下，搜索時間隨着更大的界限線性增加，如果其中一個佔優勢，則時間複雜度爲O（N）。這實際上是一個線性搜索，其中帶有「圈」，縮小線性搜索並將其間隔開並不會改變時間複雜度。在一段代碼中存在多個循環並不總是使它成爲非線性的。再次以線性搜索爲例。我們搜索一個列表，直到找到最大的元素。

//12 elements 
 
var array = [0,1,2,3,4,5,6,7,8,9,10,11]; 
 
var rows = 3; 
 
var cols = 4; 
 

 
var largest = -1; 
 

 
for(var i = 0; i < rows; ++i){ 
 

 
    for(var j = 0; j < cols; ++j){ 
 
     var checked = array[(i * cols) + j]; 
 
     if (checked > largest){ 
 
      largest = checked; 
 
     }  
 
    } 
 
} 
 
console.log("found largest number (eleven): " + largest.toString());

儘管這樣使用兩個循環而不是一個，運行時間複雜性仍然是O（N），其中N是輸入元件的數量。將它們縮小以便每個索引實際上是一個數組到多個元素，或者通過空元素分隔相關元素不會改變運行時複雜度線性約束的事實。

Answer 4

我喜歡@axiom的explanation的複雜性分析。

只是想添加可能的優化解決方案。

UPD.push（O(1)）的速度越快.concat（O(n^2)）

也在這裏是測試Array push vs. concat

const bucket = [["e","f"],[],["j", 'm', 'b'],[],["p","q"]] 
 
let totalLettersIWantBack = 4; 
 

 
//I'm starting at the end of the bucket 
 
function produceLetterArray(bucket, limit){ 
 
    let result = []; 
 

 
    for(let i = bucket.length-1; i > 0 && result.length < totalLettersIWantBack; i--){ 
 
    //previous version 
 
    //result = result.concat(bucket[i].slice(0, totalLettersIWantBack-result.length)); 
 
    
 
    //faster version of merging array 
 
    Array.prototype.push.apply(result, bucket[i].slice(0, totalLettersIWantBack-result.length)); 
 
    } 
 
    return result; 
 
} 
 

 
console.log(produceLetterArray(bucket, totalLettersIWantBack));