Урок 34
§36. Сложность вычислений
(§36. Сложность вычислений)
Содержание урока
Что такое сложность вычислений?
Что такое асимптотическая сложность?
Что такое сложность вычислений?
Центральная задача теории алгоритмов — выяснить, существует ли алгоритм решения той или иной задачи. Если существует, то возникает следующий вопрос: а можно ли им воспользоваться на практике, при современном уровне развития вычислительной техники? То есть способен ли компьютер за приемлемое время получить результат? Например, в игре в шахматы возможно лишь конечное количество позиций и, значит, только конечное количество различных партий. Следовательно, теоретически можно перебрать все возможные партии и выяснить, кто побеждает при правильной игре — белые или чёрные. Однако количество вариантов настолько велико, что современные компьютеры не могут выполнить такой перебор за приемлемое время.
Что мы хотим от алгоритма? Во-первых, чтобы он работал как можно быстрее. Во-вторых, чтобы объём необходимой памяти был как можно меньше. В-третьих, чтобы он был как можно более прост и понятен, что позволяет легче отлаживать программу. К сожалению, эти требования противоречивы, и в серьёзных задачах редко удаётся найти алгоритм, который был бы лучше остальных по всем показателям.
Часто говорят о временной сложности алгоритма (быстродействии) и пространственной сложности, которая определяется объёмом необходимой памяти. Поскольку память постоянно дешевеет, а быстродействие компьютеров растёт медленно, мы будем рассматривать главным образом временную сложность — время выполнения программы, работающей по данному алгоритму.
В общем случае, говоря о сложности алгоритма, нужно уточнить, о каком исполнителе идёт речь, какие элементарные операции мы используем. Как правило, это один из универсальных исполнителей (во многих случаях универсальным исполнителем можно считать компьютер). Временем работы алгоритма называется количество выполненных им элементарных операций Т. Такой подход позволяет оценивать именно качество алгоритма, а не свойства исполнителя (например, быстродействие компьютера, на котором выполняется алгоритм).
Как правило, величина Т будет существенно зависеть от объёма исходных данных: поиск в списке из 10 элементов завершится гораздо быстрее, чем в списке из 10 000 элементов. Поэтому сложность алгоритма обычно связывают с размером входных данных п и определяют как функцию Т(n). Например, для алгоритмов обработки массивов в качестве размера п используют длину массива. Функция Т(n) называется временной сложностью алгоритма.
Следующая страница 
Примеры
Cкачать материалы урока
