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

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

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

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

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

Big O

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

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

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

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

Sorting Big O

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

Ещё один простой пример — вложенные циклы. Вспомните как работает поиск пересечений в неотсортированных массивах. Для каждого элемента из одного массива проверяется каждый элемент другого массива (либо через цикл, либо с помощью функции in_array, чья сложность O(n), ведь в худшем случае она просматривает весь массив). Если принять, что размеры обоих массивов одинаковы и равны n, то получается, что поиск пересечений имеет квадратичную сложность или O(n^2) (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>

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

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

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

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

Получить доступ
115
курсов
892
упражнения
2241
час теории
3196
тестов

Зарегистрироваться

или войти в аккаунт

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

  • 115 курсов, 2000+ часов теории
  • 800 практических заданий в браузере
  • 250 000 студентов

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

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

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

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

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

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