Big O JS: Массивы

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

Как вы помните, алгоритмов сортировок существует много, я бы сказал очень много. Все они выполняют одну и ту же задачу, но при этом отличаются друг от друга. В информатике алгоритмы сравниваются друг с другом (или классифицируются) по их вычислительной (или алгоритмической) сложности. Сложность оценивается по количеству выполняемых операций. Понятно, что конкретное количество операций зависит от входных данных, например, если массив отсортирован, то количество операций будет минимальным (но они все равно будут, потому что алгоритм должен убедиться в том, что массив отсортирован). Если не отсортирован, то для каждого алгоритма можно подобрать такие входные данные, при которых он будет работать долго и не эффективно. Эти случаи называют соответственно верхней и нижней границей.

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

Вот некоторые примеры того, как записывается сложность: O(1), O(n), O(nlog(n)).

Sorting Big O

O(1) описывает так называемую константную сложность. Например обращение к элементу массива по индексу оценивается константой, другими словами оно не зависит от размера массива, поэтому внутри O записывается единица, символизирующая константу. А вот функция, которая печатает на экран все элементы переданного массива, используя обычный перебор имеет сложность O(n) (линейная сложность). То есть количество выполняемых операций будет равно количеству элементов массива. Именно это количество символизирует символ n в скобках.

Ещё один простой пример — вложенные циклы. Вспомните как работает поиск пересечений в неотсортированных массивах. Для каждого элемента из одного массива проверяется каждый элемент другого массива (либо через цикл, либо с помощью метода includes(), чья сложность O(n), ведь в худшем случае он просматривает весь массив). Если принять, что размеры обоих массивов одинаковы и равны n, то получается, что поиск пересечений имеет квадратичную сложность или O(n2) (n в квадрате). Существуют как очень эффективные, так и абсолютно неэффективные алгоритмы. Первые, как правило, имеют логарифмическую сложность, последние — степенную, такую, при которой n находится в степени. Скорость работы подобных алгоритмов падает с катастрофической скоростью даже при небольшом количестве элементов.

Нередко более быстрые алгоритмы быстрее не потому, что они лучше, а потому что они потребляют больше памяти или имеют возможность запускаться параллельно (и если это происходит, то работают крайне эффективно). Как и всё в инженерной деятельности, эффективность — компромисс. Выигрывая в одном месте, мы проиграем где-то в другом.

Big O

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

Вопрос эффективности кода довольно опасен. В силу того, что многие начинают учить программирование именно с алгоритмов (особенно в университете), им начинает казаться, что эффективность — это главное. Код должен быть быстрым.

Такое отношение к коду гораздо чаще приводит к проблемам, чем делает его лучше. Важно понимать, что эффективность — враг понимаемости. Такой код всегда сложнее, больше подвержен ошибкам, труднее модифицируется, дольше пишется. А главное, настоящая эффективность редко когда нужна сразу или вообще не нужна. Обычно тормозит не код, а, например, запросы к базе данных или сеть. Но даже если код выполняется медленно, то вполне вероятно, что именно тот участок, который вы пытаетесь оптимизировать, вызывается за все время жизни программы всего лишь один раз и ни на что не влияет, потому что работает с небольшим объёмом памяти, а где-то в это время есть другой кусок, который вызывается тысячи раз, и приводит к реальному замедлению.

Программисты тратят огромное количество времени, размышляя и беспокоясь о некритичных местах кода, и пытаются оптимизировать их, что исключительно негативно сказывается на последующей отладке и поддержке. Мы должны вообще забыть об оптимизации в, скажем, 97% случаев. Поспешная оптимизация является корнем всех зол. И, напротив, мы должны уделить все внимание оставшимся 3%. — Дональд Кнут

Перед тем, как пытаться что-то оптимизировать, обязательно прочитайте небольшую онлайн-книжку, которая хорошо объясняет суть всех оптимизаций.


Дополнительные материалы

  1. Big-O Cheat Sheet

<span class="translation_missing" title="translation missing: ru.web.courses.lessons.mentors.mentor_avatars">Mentor Avatars</span>

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.
Об обучении на Хекслете

Для полного доступа к курсу нужна профессиональная подписка

Профессиональная подписка откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
120
курсов
900
упражнения
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 120 курсов, 2000+ часов теории
  • 900 практических заданий в браузере
  • 360 000 студентов

Отправляя форму, вы соглашаетесь c «Политикой конфиденциальности» и «Условиями оказания услуг».

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Rambler
Логотип компании Bookmate
Логотип компании Botmother

Рекомендуемые программы

С нуля до разработчика. Возвращаем деньги, если не удалось найти работу.

Иконка программы Фронтенд-разработчик
Профессия

Фронтенд-разработчик

Разработка фронтенд-компонентов веб-приложений
4 августа 8 месяцев
Иконка программы Node.js-разработчик
Профессия

Node.js-разработчик

Разработка бэкенд-компонентов веб-приложений
4 августа 8 месяцев

Есть вопрос или хотите участвовать в обсуждении?

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы соглашаетесь c «Политикой конфиденциальности» и «Условиями оказания услуг».