这个嵌套在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

这在技术上是线性的，n 是矩阵中元素的总数。这是因为退出条件是 bucket 的长度，对于 bucket 中的每个数组，您检查是否 countOfLettersAccumulated 等于 totalLettersIWantBack。持续关注价值观。

如果您正在寻找与矩阵维度匹配的答案，它会变得更加复杂，因为看起来 bucket 的维度不固定。

您可以通过在 bucket foreach 之外添加一个额外的检查将这段代码变成常量，如果 countOfLettersAccumulated 等于 totalLettersIWantBack 然后你休息一下。

Answer 2

这里有一个技巧来解决这类问题。对于要分析其复杂性的代码，只需写出在假设不存在其他语句的最坏情况下执行每个语句 所需的时间。注意以#operations worst case:

开头的注释

对于给定的代码：

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)

请注意，随着元素数量的增加，推送操作的复杂度可能不会保持不变（最终，运行时将需要为添加的元素分配 space，并且所有现有元素可能都必须感动）。

Answer 3

这是否是二次的取决于你认为 N 是什么以及桶是如何组织的。如果 N 是字母总数，则运行时间受限于桶中的箱数（如果大于 N），或者受限于桶中字母的数量（如果 N 较大）。在任何一种情况下，搜索时间都随着较大的界限线性增加，如果一个人支配另一个人，则时间复杂度为 O(N)。这实际上是一个包含 "turns" 的线性搜索，压缩线性搜索并将其间隔开不会改变时间复杂度。一段代码中存在多个循环并不仅仅使它成为非线性的。再次以线性搜索为例。我们搜索列表，直到找到最大的元素。

//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's 的复杂性分析。

只是想添加可能的优化解决方案。

UPD .push (O(1)) is faster that .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));

这个嵌套在while循环中的for循环的时间复杂度是多少？

What is the time complexity of this for loop nested in a while loop?

javascript

big-o

computer-science

time-complexity