cdROma.me

Руководство по нотации Big O для новичков

Обозначение Big O используется в компьютерных науках для описания производительности или сложности алгоритма. Big O специально описывает наихудший сценарий и может использоваться для описания требуемого времени выполнения или пространства, используемого (например, в памяти или на диске) алгоритмом.

Любой, кто читал Programming Pearls или любые другие книги по информатике и не имеет основ математики, наткнется на стену, когда достигнет глав, в которых упоминается O (N log N) или другой, казалось бы, безумный синтаксис.

Надеюсь, эта статья поможет вам понять основы Big O и логарифмов.

Как в первую очередь программист, а во вторую - математик (а может, третий или четвертый) я обнаружил, что лучший способ полностью понять Big O - это создать несколько примеров в коде. Итак, ниже приведены некоторые общие приктики, а также описания и примеры, где это возможно.

O(1)

O(1) - описывает алгоритм, который всегда будет выполняться в одно и то же время (или пространство) независимо от размера набора входных данных.

const nums = [1, 2, 3, 4, 5];
const firstNumber = nums[0];

В нашем примере входных параметров 5, потому что в массиве 5 элементов. Для получения результата нужно выполнить одну операцию (взять элемент по индексу). Сколько операций потребуется если элементов массива будет 100? Или 1000? Или 100 000? Все равно нужна только одна операция.

O(N)

O(N) - описывает алгоритм, производительность которого будет расти линейно и прямо пропорционально размеру входного набора данных.

Пример ниже также демонстрирует, как Big O поддерживает наихудший сценарий производительности

const nums = [1, 2, 3, 4, 5];
let sum = 0;
for (let num of nums) {
  sum += num;
}

Опять зададимся вопросом: сколько операций на ввод нам потребуется? Здесь нужно перебрать все элементы, т.е. операция на каждый элемент. Чем больше массив, тем больше операций.

Используя Big O нотацию: O(n), или «сложность порядка n (order n)». Так же такой тип алгоритмов называют «линейными» или что алгоритм «линейно масштабируется».

Можем ли мы сделать суммирование более эффективным? В общем случае нет. Но если мы знаем, что массив гарантированно начинается с 1, отсортирован и не имеет пропусков? Тогда можно применить формулу:

$S = {n(n+1) \over 2}.$

, где n последний элемент массива

const sumContiguousArray = function (arr) {
  //get the last item
  const lastItem = arr[arr.length - 1];
  //Gauss's trick
  return (lastItem * (lastItem + 1)) / 2;
};
const nums = [1, 2, 3, 4, 5];
const sumOfArray = sumContiguousArray(nums);

O(N^2)

O(N^2) - представляет алгоритм, производительность которого прямо пропорциональна квадрату размера набора входных данных. Это типично для алгоритмов, которые включают вложенные итерации по набору данных. Более глубокие вложенные итерации приведут к O(N^3), O(N^4) и т. д.

const hasDuplicates = function (num) {
  //loop the list, our O(n) op
  for (let i = 0; i < nums.length; i++) {
    const thisNum = nums[i];
    //loop the list again, the O(n^2) op
    for (let j = 0; j < nums.length; j++) {
      //make sure we're not checking same number
      if (j !== i) {
        const otherNum = nums[j];
        //if there's an equal value, return
        if (otherNum === thisNum) return true;
      }
    }
  }
  //if we're here, no dups
  return false;
};
const nums = [1, 2, 3, 4, 5, 5];
hasDuplicates(nums); //true

Мы уже знаем что итерирование массива это O(N). Но у нас есть вложенный цикл, для каждого элемента мы еще раз итерируем — т.е. O(N^2) или «сложность порядка n квадрат».

Алгоритмы с вложенными циклами по той же коллекции всегда O(N^2).

O(2^N)

O(2^N) - обозначает алгоритм, рост которого удваивается с каждым добавлением к входному набору данных. Кривая роста функции O(2^N) является экспоненциальной - сначала очень мелкой, а затем стремительно поднимающейся. Примером функции O(2^N) является рекурсивное вычисление чисел Фибоначчи:

const fibonacci = function (num) {
  if (num <= 1) {
    return num;
  }
  return fibonacci(num - 2) + fibonacci(num - 1);
};
fibonacci(5); //true

O(log n)

Пример:

Двоичный поиск - это метод, используемый для поиска в отсортированных наборах данных. Он работает, выбирая средний элемент набора данных, по сути, медианное значение, и сравнивает его с целевым значением. Если значения совпадают, он вернет true. Если целевое значение выше, чем значение элемента зонда, он возьмет верхнюю половину набора данных и выполнит с ним ту же операцию. Точно так же, если целевое значение ниже, чем значение элемента зонда, он выполнит операцию с нижней половиной. Он будет продолжать уменьшать вдвое набор данных с каждой итерацией до тех пор, пока значение не будет найдено или пока он больше не сможет разделить набор данных.

Этот тип алгоритма описывается как O (log N) . Итеративное сокращение вдвое наборов данных, описанное в примере двоичного поиска, дает кривую роста, которая достигает пика в начале и медленно выравнивается по мере увеличения размера наборов данных, например, для набора входных данных, содержащего 10 элементов, требуется одна секунда, для набора данных 100 элементов занимает две секунды, а набор данных, содержащий 1000 элементов, занимает три секунды. Удвоение размера набора входных данных мало влияет на его рост, поскольку после одной итерации алгоритма набор данных будет уменьшен вдвое и, следовательно, наравне с набором входных данных вдвое меньше. Это делает такие алгоритмы, как двоичный поиск, чрезвычайно эффективными при работе с большими наборами данных.

Такой тип алгоритмов называется «разделяй и влавствуй» Divide and Conquer.

В алгоритме «бинарный поиск» на каждом шаге мы делим массив на две части.

Т.е. в худшем случае делаем столько операций, сколько раз можем разделить массив на две части. Например, сколько раз мы можем разделить на две части массив из 4 элементов? 2 раза. А массив из 8 элементов? 3 раза. Т.е. кол-во делений/операций = log2(n) (где n кол-во элементов массива).

Итоги:

Получение элемента коллекции это O(1). Будь то получение по индексу в массиве, или по ключу в словаре в нотации Big O это будет O(1)
Перебор коллекции это O(n)
Вложенные циклы по той же коллекции это O(n^2)
Разделяй и властвуй (Divide and Conquer) всегда O(log n)
Итерации которые используют Divide and Conquer это O(n log n)