Урок 20
§22. Сложность алгоритмов

Содержание урока

Как сравнивать алгоритмы?

Примеры вычисления сложности

Что такое асимптотическая сложность?

Выводы

Вопросы и задания

Как сравнивать алгоритмы?

• временная сложность	
• пространственная сложность	
• время работы алгоритма	
• асимптотическая сложность
• линейная сложность
• квадратичная сложность

Большинство задач могут быть решены по-разному, с помощью разных алгоритмов. Поэтому возникает вопрос: как выбрать лучший? И ещё один важный вопрос — способен ли современный компьютер за приемлемое время найти решение задачи? Например, в игре в шахматы возможно лишь конечное количество позиций и, следовательно, только конечное количество различных партий. Значит, теоретически можно перебрать все возможные партии и выяснить, кто побеждает при правильной игре — белые или чёрные. Однако количество вариантов настолько велико, что современные компьютеры не могут выполнить такой перебор за приемлемое время.

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

Часто говорят о временной сложности алгоритма (быстродействии) и пространственной сложности, которая определяется объёмом необходимой памяти.

Временем работы алгоритма называется количество элементарных операций T, выполненных исполнителем.

Такой подход позволяет оценивать именно качество алгоритма, а не свойства исполнителя (например, быстродействие компьютера, на котором выполняется алгоритм). При этом мы считаем, что время выполнения всех элементарных операций одинаково.

Как правило, величина Т будет существенно зависеть от объёма исходных данных: поиск в списке из 10 элементов завершится гораздо быстрее, чем в списке из 10000 элементов. Поэтому сложность алгоритма обычно связывают с размером входных данных N и определяют как функцию T(N). Например, для алгоритмов обработки массивов в качестве размера N используют длину массива. Функция T(N) называется временной сложностью алгоритма.

Временная сложность агоритма определяется функцией T(N) = 2N³. Во сколько раз увеличится время работы алгоритма, если размер данных N увеличится в 10 раз?

Пространственная сложность — это зависимость объёма занимаемой памяти от размера данных N. Для ускорения работы некоторых алгоритмов нужно использовать дополнительную память, которая может быть намного больше, чем память для хранения исходных данных.

Для быстрой сортировки массива из N элементов с помощью алгоритма Семёна требуется N вспомогательных массивов, каждый из которых содержит N элементов. Как изменится объём нужной дополнительной памяти, если N увеличится в 10 раз?

Поскольку память постоянно дешевеет, а быстродействие компьютеров растёт медленно, более важна временная сложность алгоритмов. Пространственную сложность мы дальше рассматривать не будем.

Следующая страница Примеры вычисления сложности

Cкачать материалы урока