Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Big O JS: Массивы

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

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

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

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

Sorting Big O

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

Что такое худший случай? В зависимости от того в каком состоянии находятся начальный массив, количество операций будет разным даже при условии что массив одного и того же размера. Чтобы проще понять, возьмем в качестве аналогии Кубик Рубика. Количество операций (действий) которые нужно проделать для сборки кубика рубика зависит от того, в каком положении находятся его грани перед сборкой. В некоторых случаях действий понадобится мало, в других много. И вот та ситуация, в которой таких действий понадобится больше всего, и называется худшим случаем. Алгоритмическая сложность всегда оценивается по худшему случаю для выбранного алгоритма.

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

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

Big O

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

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

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

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

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


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

  1. Big-O Cheat Sheet

Аватары экспертов Хекслета

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

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

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

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

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

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

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

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

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

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

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

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

  • 130 курсов, 2000+ часов теории
  • 900 практических заданий в браузере
  • 360 000 студентов
Даю согласие на обработку персональных данных, соглашаюсь с «Политикой конфиденциальности» и «Условиями оказания услуг»

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

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff
Рекомендуемые программы

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

Иконка программы Фронтенд-разработчик
Профессия
Разработка фронтенд-компонентов веб-приложений
1 июня 10 месяцев
Иконка программы Node.js-разработчик
Профессия
Разработка бэкенд-компонентов веб-приложений
1 июня 10 месяцев
Иконка программы Fullstack-разработчик
Профессия
Новый
Разработка фронтенд и бэкенд компонентов веб-приложений
1 июня 16 месяцев

Используйте Хекслет по максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

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

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