这个解决方案的时间复杂度是多少 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);是将一个数字从10进制转换为2进制字符串，这是我迭代的。

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 系数。

Answer 2

我同意 O(n) 但实际上它取决于 parseInt 函数的实现。

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

What is time complexity of this solution O(N) or O(LogN)?

javascript

algorithm

asymptotic-complexity