javascript - 这个解决方案的时间复杂度是多少 O(N) 或 O(LogN)？

Question

https://codility.com/programmers/lessons/1-iterations/

考虑到这一点:

if (largestHole > (bin.length - i) && subHole < (bin.length - i)) {
  break;
}

如果到目前为止最大孔的长度小于要检查的剩余数字的长度，则它会打破循环

这一行 let bin = parseInt(N, 10).toString(2); 是将一个数字从 base 10 转换为 base 2 string，这是我迭代的。

function solution(N) {
  let bin = parseInt(N, 10).toString(2);
  let subHole = 0;
  let largestHole = 0;
  for (var i = 0; i < bin.length; i++) {
    if (largestHole > (bin.length - i) && subHole < (bin.length - i)) {
      break;
    }
    if (bin[i] === '0') { subHole++; }
    else {
      if (subHole > largestHole) {
        largestHole = subHole;
      }
      subHole = 0;
    }
  }
  return largestHole;
}

https://codility.com/programmers/lessons/1-iterations/

Answer 1

仍然是 O(n)。复杂度不考虑系数。此外，O(log n) 函数类似于二进制搜索。

编辑: O(log n) 算法的简单解释:以二分查找为例。例如，你有一个从 1 到 100 的数字 x，它隐藏在一个包含 n 个从 1 到 100 的数字的排序数组中。你从数组的中间开始，取决于中间数字与 x 相比的大小，你搜索数组的左半部分或右半部分。该过程递归地继续，直到您找到该数字。

例如我想在 [1,3,5,6,7,9,10] 中找到 5。我从第四名开始。是6，大于5，所以我们搜索左半边，从1到5。然后，我再次检查缩小范围内的中间位置，即3。它小于5，所以我们搜索右半边。此时我们只剩下一个数字 - 即 5。

搜索一直将数组分成两半，因此最坏的情况将采用 log 2 n(n 的以 2 为底的对数)。这是一个 O(log n) 函数。

但是，正如我所说，复杂度的系数并不重要。例如冒泡排序通常需要大约 (n^2)/2 轮，但我们只是将其计算为 O(n^2)，忽略 1/2 系数。