Какова временная сложность этого решения 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) алогрита: возьмем, например, бинарный поиск. У вас есть число x, скажем, от 1 до 100, и оно скрыто в отсортированном массиве, содержащем n чисел от 1 до 100. Вы начинаете с середины массива, в зависимости от размера среднего числа по сравнению с x, вы искать левую или правую половину массива. Процесс продолжается рекурсивно, пока вы не найдете номер.

Например, я хочу найти 5 в [1,3,5,6,7,9,10]. Я начинаю с 4-го места. Это 6 и больше 5, поэтому мы ищем левую половину от 1 до 5. Затем я снова проверяю среднюю позицию в суженном диапазоне, который равен 3. Он меньше 5, поэтому мы ищем правую половину. На данный момент у нас осталось только одно число - 5.

Поиск продолжает делить массив пополам, поэтому в худшем случае log 2 n (логарифм по основанию 2 из n). Это функция O(log n).

Однако, как я уже сказал, коэффициент сложности не имеет значения. Например, Bubble sort обычно занимает приблизительно (n^2)/2 оборота, но мы просто считаем это как O(n^2), игнорируя коэффициент 1/2.

Answer 2

Я согласен с O(n), но на самом деле это зависит от реализации функции parseInt.