Алгоритмы и структуры данных #1 — Оценка сложности алгоритмов

 Сегодня мы начнем проходить новый цикл уроков, посвященных алгоритмам и структурам данных. Это невероятно важная область IT-технологий, которая часто используется в большинстве современных программ. Алгоритмы сейчас используются практически повсеместно: начиная от небольших программ и заканчивая гигантскими проектами. Алгоритмы сортировки, шифрования, сжатия, поисковые алгоритмы, а также алгоритмы обработки больших данных, поиска кратчайшего пути и многие другие — все они знакомы едва ли не каждому программисту и играют большую роль при написании проектов. Их все мы обязательно изучим. Также мы затронем структуры данных, без знания которых невозможно эффективно обрабатывать информацию. Будет очень интересно.

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

Понятие алгоритмической сложности

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

Сложность алгоритма всегда зависит от объема входных данных. Довольно очевидно, что если какому-то алгоритму дать на обработку 10 значений, то он справится быстрее, чем алгоритм со 100 значениями. Однако стоит иметь в виду, что в таком случае оценка сложности получится очень приблизительной, поскольку она зависит и от других факторов: мощности процессора, объема оперативной памяти, типа данных или языка программирования. Поэтому на практике всегда вычисляют асимптотическое значение сложности, то есть когда объем входных данных стремится к бесконечности. В таком случае легко дать универсальную оценку сложности для любого алгоритма.

В общем случае сложность любого алгоритма определяется количеством операций, которое необходимо совершить, чтобы обработать n входных данных. Допустим, для обработки n данных нужно совершить 10n? + 5n операций. Если мы будем увеличивать n до бесконечности, то сложение с 5n и умножение на 10 практически не будет влиять на скорость выполнения. Наибольшее влияние будет оказывать возведение в степень, поэтому при вычислении сложности умножение на число и сложение опускают. В нашем примере вычислительная сложность будет равна O(n?). Говорят, что сложность алгоритма кубически зависит от размера входных данных. При оценке большого выражения всегда оставляют самую быстрорастущую функцию. В данном случае буква O означает асимптотическую сложность. А вся эта запись говорит программисту, что зависимость скорости выполнения алгоритма от входных данных будет аналогична графику функции n?. Давайте теперь посмотрим на основные случаи оценки сложности.

Основные случаи оценки сложности

1. O(1) — так обычно пишут, если время работы алгоритма вообще не зависит от входных данных и всегда постоянно. Такое случается, если нам нужно просто извлечь какой-либо элемент из массива. Для этого нам не нужно анализировать каждый элемент или проводить какие-либо операции. Мы просто дожидаемся появления нужного элемента и получаем его значение. Данный вид алгоритмов самый быстрый из всех.
2. O(log n) — это логарифмическая сложность. В данном случае от размера входных данных берется логарифм по основанию 2. Если алгоритм обрабатывает 8 значений, то сложность будет равна O(3), а если 256, то — O(8). Где это используется? Например, при поиске в массиве элемента с определенным значением. Массив должен быть предварительно отсортирован по возрастанию. Тогда мы можем взять центральный элемент и сравнить с нужным нам значением. Если центральный элемент меньше, то отбрасываем левую половину массива, а если больше — правую. Затем ту же операцию проводим внутри оставшейся половины, и так далее, пока мы не дойдем до интересующего нас элемента. Чтобы найти нужный элемент в массиве из 8 элементов, нужно выполнить максимум 3 сравнения, то есть 3 операции. Поэтому такой алгоритм будет обладать логарифмической сложность, так как log 8 = 3. Этот вид алгоритмов выполняется чуть дольше предыдущего, но является одним из лучших.
3. O(n?) — квадратическая сложность. Например, такой сложностью обладают алгоритмы, где один цикл для n элементов вложен внутрь другого цикла для n элементов. Таким образом, для каждого из n элементов нужно провести еще n операций, то есть всего n * n = n?. Этот вид алгоритмов выполняется уже заметно дольше двух предыдущих.

Существуют и другие варианты сложности алгоритмов. Приведу для этого небольшую сравнительную таблицу, где алгоритмы будут указаны по возрастанию сложности сверху вниз.

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

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

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

Источник: https://tproger.ru

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

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

На этом сегодня все. Надеюсь, вам понравился этот урок и сама идея курса по алгоритмам и структурам данных. Начиная со следующего урока, мы уже будем изучать реальные алгоритмы и смотреть на практические примеры. И для каждого из рассматриваемых алгоритмов я буду приводить их вычислительную сложность, чтобы вы понимали, насколько он будет эффективен при разработке. Спасибо за внимание :)

Источник: m.vk.com

Комментарии: