嵌套在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));