javascript - 堆叠循环的重要之处是什么？

Question

当您的函数有多个非嵌套循环时，时间复杂度会从 O(N) 改变吗？我知道如果你要写一个函数来记录数组的每个元素，你可以用一个循环来完成，给你一个 O(N) 的 bigO，但是如果你添加更多的循环，那会给你一个 bigO O(N *循环数)？

考虑这个字符串压缩函数，它是什么 bigO，因为它多次循环遍历字符串:

 function compression(string) {
  let compressed = "";
  let map = {

  }

  string.split("").forEach((e, i) => {
    map[e] = 0;
  })

  string.split("").forEach((e, i) => {
    map[e] += 1;
  })

  for (var element in map) {
    compressed += element + map[element];
  }
  if (compressed.length > string.length) {
    return string;
  } else {
    return compressed;
  }
}

Answer 1

关于非嵌套循环，如您所展示的那些，时间复杂度仍为 O(N)。这是因为循环次数是一个常量——例如，如果你运行 N 个元素 3 次，在大 O 表示法中你可以删除常量。因此，它仍然是 O(N)。

注意:这里假设循环次数是一个常数。如果循环的数量以任何方式取决于元素的数量，那么您将需要考虑这种关系。