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

Алгоритмическая сложность Основы алгоритмов и структур данных

Мы уже поняли, что задачи можно решать "быстро" или не очень, но алгоритмов решения одной задачи существует множество, из чего исходит потребность их сравнивать. Сравнивать мы можем такие показатели как скорость вычисления и память, требуемая для решения задачи.

Скорость (вычислительная сложность) - количество действий которые мы должны будем совершить. Память (пространственная сложность) - количество памяти которые мы будем выделять для этого алгоритма. Чаще нас будет интересовать первый показатель.

Эти показатели зависят от входных данных. Обозначим входные данные как n и опишем зависимость. Например, алгоритм по перебору всех элементов массива - f(n), на графиках f(n) будет выглядеть так:

n

В массиве с 1 элементом, мы выполним 1 действие, с 30 элементами, 30 действий. То есть с увеличением n, наша скорость выполнения будет расти линейно.

Поиск повторяющихся элементов в массиве. Берем элемент массива и проходимся по всему массиву, сравнивая его со всеми элементами. Допустим, массив длинной 5, каждый элемент должен будет пройти по всей длине, то есть 5 раз (элемент сам с собой тоже будем сравнивать, для простоты), итого 5 элементов, на каждый 5 действий, это 52. Или f(n2).

n^2

Добавление элементов в массив. Вне зависимости от длины массива скорость будет одинаковой f(1)

1

Самая популярная - логарифмическая зависимость f(log(n)).

log

В информатике вы постоянно будете видеть log(n). Договоримся, что у всех этих логарифмов основание = 2. Бинарный поиск из первого урока — наглядный пример f(log(n)). Массива длинной n элементов требует log(n) действий.

В работе в основном мы столкнёмся с тривиальными сложностями, которые описаны на рисунке

O

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

Теперь мы будем говорить, скорость алгоритма Сортировки слиянием не n * log n, а O(n * log n)

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

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

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

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