Нотация Big O позволяет нам измерять временную и пространственную сложность нашего кода.
Подумайте о примере цикла for. Вы можете запустить его над массивом из 5 элементов, и он будет работать довольно быстро, но если вы запустите его над массивом из 10 000 элементов, время выполнения будет намного медленнее. См. Пример:
Обозначение Big O позволяет нам определить, сколько времени потребуется для выполнения алгоритма. Это позволяет нам понять, как будет масштабироваться фрагмент кода. Он измеряет алгоритмическую эффективность.
O(1)
Это известно как постоянное время. Время согласовано для каждого исполнения. Представьте, что вы работаете на заправке. Чтобы заправить автомобиль, у вас уходит ровно 25 секунд, после чего эта конкретная задача считается выполненной. Неважно, заправляете ли вы в этот день одну машину или сто машин, вы заправляете машину за постоянный промежуток времени.
Итак, в нашем примере выше нас не интересуют O (1), O (2) и т. Д. Мы округляем его до O (1), что означает, что наша операция представляет собой плоскую линию с точки зрения масштабируемости. На это уйдет столько же времени. Это предсказуемо и очень масштабируемо. См. Пример:
O(n)
Наш пример цикла - O (n), поскольку он выполняется для каждого значения во входных данных. Количество операций увеличивается линейно в соответствии с входными данными. (n) представляет количество входов. Алгоритм работает за линейное время.
O(n²)
Скажем, мы хотим зарегистрировать серию пар из массива элементов. Сделать это можно так:
Хорошее эмпирическое правило состоит в том, что если вы видите вложенные циклы, вы используете умножение, чтобы выработать нотацию. Итак, в нашем примере выше мы делаем O (n * n), которое становится O (n²) (O из n в квадрате). Это известно как квадратичное время, что означает, что каждый раз, когда количество элементов увеличивается, мы увеличиваем операции квадратично.
На самом деле вы хотите избежать кода, который выполняется за O (n²), поскольку количество операций значительно увеличивается, когда вы вводите больше элементов.
Расчет большого числа
Чтобы вычислить Big O, вы можете просмотреть каждую строку кода и определить, является ли это O (1), O (n) и т. Д., А затем вернуть результат в конце. Например, это может быть O (4 + 5n), где 4 представляет четыре экземпляра O (1), а 5n представляет пять экземпляров O (n).
Однако есть более простой способ рассчитать это, и это делается с помощью следующих четырех правил:
- Предположим худшее
- Удалить константы
- Используйте разные термины для входных данных
- Отбросьте любые недоминанты
Принимая каждое из них по очереди:
- Допускать худшее
Рассчитывая Big O, вы всегда думаете о худшем случае. Например, если вы перебираете массив и ищете элемент, это может быть первый элемент или последний. Поскольку мы не уверены, в этом случае мы должны принять O (n).
2. Удалить константы.
Это немного сложнее, но потерпите меня. Рассмотрим этот код:
У нас есть функция, которая делает несколько вещей. Некоторые - O (1), например строка 3, а другие - O (n), например строка 9.
Мы могли бы выразить эту нотацию как O (1 + n / 2 +100), но на самом деле это слишком конкретно. Мы можем удалить наши операции O (1), потому что, как показывает опыт, они, вероятно, будут незначительными по сравнению с нашими операциями O (n). Если мы предоставляем миллион элементов в нашем входном массиве, то дополнительные 100 операций из O (1) не являются нашей основной проблемой.
Итак, у нас есть O (n / 2) - по мере того, как n становится все больше и больше, деление его на два имеет убывающий эффект. Таким образом, в конечном итоге наша нотация Big O для этой функции становится O (n).
3. Различные термины для входных данных
Если бы мы дважды выполняли цикл для одного и того же массива, тогда наш Big O технически был бы O (2n), но давайте отбросим константы, так что у нас останется O (n). Но теперь нам нужно подумать о других терминах для входных данных. Что это обозначает?
Если мы посмотрим на приведенный выше код, мы увидим, что теперь у нас есть два входа. Один может состоять из одного элемента, а другой может содержать миллион элементов. Итак, наша функция больше не O (n), это O (a + b). n, который мы используем в нашей нотации, произвольный, поэтому нам нужно отразить оба ввода в нашей нотации.
В этом случае наши циклы не вложены. Если бы это было так, то наш код был бы O (n²), что могло бы стать потенциальной целью для рефакторинга. Обычно, если есть вложенные циклы, вы умножаете, а не добавляете переменные.
4. Удалите недоминантные термины.
Взгляните на этот код:
Итак, у нас есть один цикл вверху, который равен O (n), а затем вложенный цикл, который равен O (n²). Таким образом, наша сумма составляет O (n + n²). Но, как мы видели в правиле № 2, мы хотим отказаться от констант. Итак, какой из двух терминов для нас важнее?
В этом случае мы отбрасываем O (n) и оставляем O (n²), поскольку это более важно. Это доминирующий термин, поскольку он гораздо сильнее влияет на производительность.
Заключение
Так в чем же смысл?
Если мы знаем, что будем иметь дело только с небольшими затратами, тогда Big O не имеет особого значения. Но при написании кода следует учитывать его масштабируемость.
Обращая внимание на Big O, вы смотрите в будущее и с большей вероятностью напишете код, который можно эффективно масштабировать. Вы можете начать оценивать стоимость вашего кода и делать осознанный выбор в том, как вы его пишете.
Ресурсы
