Во многих языках программирования часто существует несколько способов выполнения одной и той же задачи, особенно это касается JavaScript. Поэтому, чтобы обсудить сравнение нескольких реализаций одной и той же функции или другого кода, выполняющего одну и ту же задачу, мы используем нотацию Big O.
Приведенная выше диаграмма пока не имеет особого смысла, однако я надеюсь, что к концу этой статьи у вас будет достаточно понимания Bio O, чтобы понять общие отображаемые тенденции.
Big O также полезен при обсуждении компромиссов между подходами, а также для поиска слабых мест в вашем коде. Не забываем ИНТЕРВЬЮ! Практически всегда, особенно если у вас остается время, вас попросят рассказать об эффективности вашего кода, и именно тогда вы сможете позволить своим знаниям о BioO проявить себя.
В целом, Bio O - это не то, чего мы можем избежать в программировании, но, похоже, это одна из самых сложных тем, так что давайте сразу приступим к ней!
Мы используем большую нотацию O, чтобы обсудить временную и пространственную сложность нашего кода. Временная сложность - это то, как мы анализируем время выполнения алгоритма по мере увеличения размера входных данных. Сложность пространства - это объем дополнительной памяти, необходимый для выполнения кода в нашем алгоритме. Что касается сложности пространства, важно отметить, что мы имеем в виду сложность вспомогательного пространства, которая относится к пространству, требуемому алгоритмом НЕ, включая пространство, занимаемое входными данными.
Я также рассмотрю логарифмы, так как есть некоторые алгоритмы, которые включают журналы, такие как сортировка, поиск и иногда рекурсия. Я не буду слишком углубляться в математику, но это то, что мы должны иметь в виду. Из-за того, что Bio O и оптимизация - довольно большая тема, это скорее часть 1 для серии статей.
Как рассчитать сложность Bio O of Time?
Проще говоря, мы подсчитываем количество простых операций, которые должен выполнить компьютер. Это имеет больше смысла, чем время выполнения самого кода с использованием встроенных таймеров, потому что разные компьютеры могут отличаться по времени обработки, и это не является правильной оценкой времени выполнения кода. Когда мы считаем простые операции, это остается неизменным, независимо от того, на каком компьютере мы работаем.
Вот несколько примеров сред выполнения (их намного больше, но эти 3 являются наиболее распространенными):
- Константа: f (n) = 1 → O (1)
- Линейный: f (n) = n → O (n)
- Квадратичный: f (n) = n² → O (n²)
Как посчитать количество простых операций?
- Константы не имеют значения, потому что они не отнимают время. Примеры:
a. Арифметические операции (+, -, *, \)
b. Присвоение переменной (let, const, var)
c. доступ к элементам в массиве по индексу или к объекту по ключу - Циклы сложны: сложность - это длина цикла умноженная на сложность всего, что находится внутри цикла.
Как рассчитать сложность Bio O Space?
Мы можем рассчитать сложность вспомогательного пространства с помощью нескольких практических правил:
- Самые примитивные типы данных, такие как логические, числа, null, undefined) считаются постоянным пространством.
- Строки требуют пространства O (n), где n - длина строки.
- Типы ссылок также обычно O (n), где n - длина массивов или ключей для объектов.
Логарифмы
Логарифм - это величина, обратная возведению в степень. Вы можете использовать множество баз. Распространенным является двоичный логарифм, который является логической базой 2. При написании нотации Bio O, которая включает журналы, мы склонны опускать базу, даже если при написании регулярных выражений журнала мы должны ее включать.
Логарифм (основание 2) числа примерно измеряет количество раз, которое вы можете разделить это число на 2, прежде чем вы получите значение, которое меньше или равно единице (≤1)
