Если видео недоступно для просмотра, попробуйте выключить блокировщик рекламы.

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

В информатике алгоритмы сравниваются друг с другом (или классифицируются) по их вычислительной (или алгоритмической) сложности. Сложность оценивается по количеству выполняемых операций.

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

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

image

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

Еще один простой пример — вложенные массивы. Если вывод на экран одного массива занимает n операций, то для вывода на экран массива массивов понадобится n по n операций, то есть n * n = n^2. Запись в нотации будет выглядеть как O(n^2).

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

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

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

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

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


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

  1. Big-O Cheat Sheet
Мы учим программированию с нуля до стажировки и работы. Попробуйте наш бесплатный курс «Введение в программирование» или полные программы обучения по Node, PHP, Python и Java.

Хекслет

Подробнее о том, почему наше обучение работает →