Вы когда-нибудь хотели подсчитать, насколько эффективен ваш код? Что ж, вы можете! Использование нотации Big O! Хотя это предмет компьютерных наук, если вы обнаружите, что у вас нет степени в области компьютерных наук, вы, возможно, узнали об этом, пока искали способы написать лучший код. Это также отличный способ обсудить эффективность алгоритмов среди других разработчиков.
Что это
Обозначение Big O используется для математического описания сложности алгоритма; особенно наихудший сценарий или «верхняя граница». Он не отвечает на вопрос «Сколько времени потребуется этому алгоритму для обработки такого количества данных в секундах?». Это всегда будет зависеть от среды и оборудования. Вместо этого он отвечает на вопрос "Каковы темпы роста количества операций, которые должен выполнить алгоритм?".
«Каковы темпы роста количества операций, которые должен выполнить алгоритм?»
На что это похоже
Их больше, но я расскажу об основных.
Расчет большого числа
Так как же узнать, какой у вас блестящий новый код - постоянный или квадратичный? Давайте посмотрим на несколько примеров кода:
Константа O (1) - самая быстрая
Константы выполняют одинаковое количество операций независимо от размера ввода. Мы всегда знаем наихудший сценарий, поэтому он не увеличивает темпы роста. По этой причине в наших расчетах Big O константы опускаются или игнорируются. Это часто называется отбрасыванием недоминантных членов.
Вышеупомянутая функция head имеет единственную постоянную операцию; всегда извлекает первый элемент массива.
Логарифмический O (log n)
Классическим примером логарифма (журнала) является двоичный поиск. Шаблон двоичного поиска делит ввод на каждой итерации, инвертируя экспоненту (что означает, что вместо умножения на себя, он делит сам себя). Другими словами, по мере выполнения каждой итерации набор данных и, следовательно, количество операций становится меньше.
Здесь мы используем рекурсию хвостового вызова для функции двоичного поиска findIndexOfNumber. Все операции внутри функции имеют сложность O (1), за исключением случаев, когда мы снова вызываем функцию findIndexOfNumber. Как объяснено в первом примере, операции O (1) исключаются из вычислений, поэтому остается log n, поскольку n уменьшается с каждой итерацией.
Линейное O (n)
Количество операций, имеющих линейную временную сложность, увеличивается пропорционально их вводу. Для вычисления Big O не имеет значения, если ваша функция возвращается раньше времени, Big O всегда рассматривает худший случай.
Обе эти функции равны O (n). Мы перебираем массив один раз, и количество раз, которое нам нужно сделать, зависит от размера массива.
Другие методы в этих функциях, toUpperCase и push, - O (1). Они не увеличивают темпы роста операций, но что волнует Big O? Худший сценарий, который здесь O (n). Вот что это за функции.
Логарифмический линейный O (n * log n)
Логлинейные функции находятся на полпути между быстрым и медленным, и большинство производительных функций сортировки относятся к этому типу, но не все. Например, если мы возьмем наш двоичный поиск сверху и используем его для нахождения индекса каждого числа в массиве, мы получим логарифмическую линейную сложность:
Квадратичный O (n²)
Функция имеет квадратичную сложность, когда ей необходимо выполнить линейную операцию O (n) для каждого значения во входных данных. Хороший способ обнаружить такой - это дважды перебирать входные данные, например, во вложенных циклах (таким образом, ^ 2).
Выше duplicatesPresent отвечает за получение массива имен пользователей и выяснение, появляются ли они в массиве более одного раза. Для этого он перебирает `usernames` и для каждого имени снова перебирает его, чтобы проверить, есть ли другие вхождения.
Экспоненциальный O (2 ^ n)
Вы можете представить себе экспоненциально сложную функцию как противоположность логарифма, потому что это именно то, чем она является. Для каждых входных данных скорость операций удваивается. Ура! Нетрудно понять, почему это не так, когда дело касается производительности. Итак, каковы примеры экспоненциально сложных алгоритмов? Наиболее известен алгоритм взлома паролей методом «грубой силы». Вот почему вам рекомендуется делать пароли длинными и случайными, так как стоимость вычисления того, какой это может быть, растет экспоненциально. Рекурсивная функция Фибоначчи также сделает это:
Если вы когда-нибудь захотите остановить свою мощную дорогую машину разработки, просто запустите ее.
Вы можете подумать, что здесь используется рекурсия, как в ранее упомянутой функции logarithm findIndexOfNumber, так почему эта функция намного сложнее? Как уже упоминалось, findIndexOfNumber использует рекурсию хвостового вызова по сравнению с простой рекурсией ole ’в fibonacci. Здесь интерпретатор должен учитывать результат каждого вызова fibonacci, потому что мы используем результат для сложения. В findIndexOfNumber нам не нужен результат для каких-либо действий, поэтому интерпретатор может безопасно удалить вызов из стека и обработать следующий.
Факториал O (n!) - самый медленный
Мне нравится, что в обозначении факториалов стоит восклицательный знак! Это самый медленный и сложный из всех алгоритмов, поэтому восклицательный знак кажется подходящим. Это функции, которые умножают число на каждое число под ним. Итак, факториал 5 (5!):
1×2×3×4x5 = 120
Увеличение размера данных значительно усложняет задачу, но это трудно визуализировать, просто глядя на произведение чисел. Как факториалы выглядят в реальном мире? Чаще всего встречаются коммивояжер и проблемы с маршрутизацией трафика:
Учитывая список городов и расстояния между каждой парой городов, каков самый короткий маршрут, который посетит каждый город ровно один раз и вернется в исходный город? - Проблема коммивояжера - распространенный фактор
Посмотрите, как трудно узнать ответ на этот вопрос, не принимая во внимание ВСЕ возможные комбинации, и как это становится хуже, чем больше городов (или людей) вы добавляете? Чем больше «чисел» вам нужно
для умножения?
Существует больше нотаций Big O, чем я перечислил здесь, но я считаю, что они дают хорошее представление о тех, которые с большей вероятностью встретятся. Надеюсь, теперь вы можете более внимательно изучить свой код и понять, почему он работает или не работает, а также у вас есть язык для обсуждения сложности алгоритма с коллегами.
