§ 23. Понятие правильности и сложности алгоритма
| Сайт: | Профильное обучение |
| Курс: | Информатика. 10 класс (Повышенный уровень) |
| Книга: | § 23. Понятие правильности и сложности алгоритма |
| Напечатано:: | Гость |
| Дата: | Среда, 8 Май 2024, 22:07 |
23.1. Сложность алгоритма
|
Основным показателем сложности (трудоемкости) алгоритма является время, необходимое для решения задачи, и объем требуемой памяти. Существуют понятия сложности в худшем и среднем случае. Обычно оценивают сложность в худшем случае. Временная сложность в худшем случае — функция от размера входа, равная максимальному количеству операций, выполненных в ходе работы алгоритма при решении задачи данного размера. Емкостная сложность в худшем случае — функция от размера входа, равная максимальному количеству памяти, к которому было обращение при решении задач данного размера. При анализе сложности для класса задач определяется некоторое число, характеризующее объем данных, которое требуется для представления входных данных задачи. Это величина называется размер входа. Можно сделать вывод, что сложность алгоритма — функция размера входа. Размер входа может зависеть как от числа входных данных, так и от величины входных данных (пример 23.1). Одним из упрощенных видов анализа, используемых на практике, является асимптотический анализ алгоритмов. Целью асимптотического анализа является сравнение затрат времени и других ресурсов различных алгоритмов, предназначенных для решения одной и той же задачи, при больших объемах входных данных. Используемая в асимптотическом анализе оценка функции трудоемкости, называемая сложностью алгоритма, позволяет определить, как быстро растет трудоемкость алгоритма с увеличением объема данных. В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе. Чтобы определить сверху трудоемкость алгоритма, используется обозначение O, читается «о большое» (пример 23.2). Иногда при анализе алгоритма приходится учитывать не только максимальное, но и минимальное количество операций, необходимое для решения задачи. В этом случае используется обозначение Существует ряд важных практических причин для анализа алгоритмов. Одной из них является необходимость получения оценок или границ для объема памяти, или времени работы, которое потребуется алгоритму для успешной обработки конкретных данных. Машинное время и память — относительно дефицитные (и дорогие) ресурсы, на которые часто одновременно претендуют многие пользователи. Всегда следует избегать прогонов программы, отвергаемых системой из-за нехватки запрошенного времени. Теоретический анализ способен выявить узкие места в программах. Иногда невозможно составить четкое мнение об относительной эффективности двух алгоритмов. Один может в среднем лучше работать, к примеру, на случайных входных данных, в то время как другой лучше работает на каких-то специальных входных данных. Будем пользоваться следующим критерием для оценки качества алгоритма: чем медленнее растет функция f(n) на каком-то участке области , тем алгоритм будет более эффективным (пример 23.3). Этот критерий основан на времени работы в худшем случае, но аналогичный критерий может быть также определен для среднего времени работы. При разработке алгоритма необходимо стремиться к тому, чтобы рост функции f(n) для алгоритма был как можно медленнее на той области, на которой требуется получить решение. Однако здесь могут возникать определенные трудности.
|
Пример 23.1. Оценка сложности поисковых алгоритмов. Линейный поиск Нахождение информации в неотсортированной структуре данных, например в массиве, требует применения последовательного поиска. Последовательный поиск в среднем случае выполнит проверку n/2 элементов, а в худшем — элементов. При этом предполагается, что сравнение двух чисел выполняется за 1 операцию. Бинарный поиск Этот метод поиска значительно эффективнее, чем последовательный поиск, но требует, чтобы данные были предварительно упорядочены (отсортированы). В худшем случае выполняется не более log2n, в связи с чем метод еще называется логарифмическим поиском. Пусть n — размер входных данных. Оценка сложности алгоритма f(n) = 0(g(n)), если при g > 0 и n > 0 существуют такие положительные C, n0, что f(n0) ≤ C * g(n0) . Другими словами, скорость роста функции f при достаточно больших n не выше скорости роста функции g.
Оценка сложности алгоритмов сортировки.
Для метода сортировки обменом оценка трудоемкости составляет — O(n2). Это означает, что количество операций при сортировке элементов не превосходит величину C · n2 при некотором значении коэффициента C, который не зависит от n. Для быстрой сортировки оценка трудоемкости составляет в среднем — O(nlog2n). Это означает, что количество операций при сортировке элементов не превосходит величину C · nlog2n при некотором значении коэффициента C, который не зависит от n. Оценка в худшем случае такая же, как для сортировки обменом. Пусть — размер входных данных. Оценка сложности алгоритма f(n) = если при g > 0 и n > 0 существуют такие положительные c, n0, что f(n0) ≥ c * g(n0),. Другими словами, скорость роста функции f при достаточно больших не ниже скорости роста функции g. Пример 23.3. Возможные оценки качества алгоритма. Константный алгоритм — O(1) Порядок роста O(1) означает, что вычислительная сложность алгоритма не зависит от размера входных данных. Единица в формуле не значит, что алгоритм выполняется за одну операцию или требует очень мало времени. Важно то, что это время не зависит от входных данных. Линейный алгоритм — O(n) Порядок роста O(n) означает, что сложность алгоритма линейно растет с увеличением входного массива. Если линейный алгоритм обрабатывает один элемент пять миллисекунд, то мы можем ожидать, что тысячу элементов он обработает за пять секунд. Например, линейный поиск. Логарифмический алгоритм — O(logn) Порядок роста O(logn) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива. При анализе алгоритмов по умолчанию используется логарифм по основанию 2. Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность. Например, бинарный поиск. Линейно-логарифмический алгоритм — O(nlogn) Линейно-логарифмический алгоритм имеет порядок роста O(nlogn). Некоторые алгоритмы типа «разделяй и властвуй» попадают в эту категорию. Например, быстрая сортировка (в среднем) или метод sort в STL. Квадратичный алгоритм — O(n2) Время работы алгоритма с порядком роста O(n2) зависит от квадрата размера входных данных. Например, если массив из тысячи элементов потребует 1 000 000 операций, то массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, квадратичный алгоритм будет обрабатывать миллион элементов 32 года. Например, сортировка обменом. Полиномиальный алгоритм — O(nk) О полиномиальной сложности (порядка k) говорят тогда, когда время работы алгоритма растет не быстрее, чем полином k-й степени от n. Экспоненциальный алгоритм — O(2n), O(en), O(nn) и др. Если время работы алгоритма растет не медленнее, чем экспонента от n, то говорят об экспоненциальном алгоритме. |
, читается «омега».23.2. Правильность алгоритма
|
Алгоритм обладает свойством массовости, т. к. исходными данными для него может быть любая конечная последовательность символов. Алгоритм не обладает этим свойством, если он работает лишь на ограниченном наборе исходных данных, но на остальных наборах не работает или работает неправильно. Под свойством правильности понимается соответствие результатов работы алгоритма условию задачи. Проверить свойство правильности некоторых алгоритмов достаточно просто, для этого можно взять несколько примеров исходных данных, для которых результат очевиден, и протестировать алгоритм на них, но доказать правильность алгоритма достаточно сложно, так как его необходимо проверить на всех возможных наборах данных (а их в силу массовости может быть очень много). Доказательство правильности алгоритма называется верификацией. Доказательство правильности алгоритма — один из наиболее трудных, а иногда и особенно утомительных этапов создания алгоритма Идея математического доказательства корректности программ (верификации) обычно сводится к доказательству того факта, что программа (подпрограмма) является корректной относительно ее входной и выходной спецификации. Наиболее известный метод, называемый методом индуктивных утверждений, был предложен в 1967 г. Флойдом, хотя сама идея его восходит к Тьюрингу (1950). Доказательство правильности построенного алгоритма не может быть проведено экспериментально, т. е. с помощью прогона программы, реализующей данный алгоритм на различных тестах. Необходимо строгое математическое доказательство правильности. Прогон программы на разных тестах позволяет провести доказательство правильности работы программы в целом. Этот прием — самая распространенная процедура доказательства правильности программы. Считается, что программа работает правильно, если выданные ей ответы могут быть подтверждены известными методами или вычислены вручную. |
Принцип верификации был выдвинут Венским кружком в 20-е гг. XX в. Члены кружка полагали, что в науке должны остаться два класса научных предложений — аналитические истины, не имеющие предметного содержания, и фактические истины, эмпирические факты конкретных наук, значение которых может быть проверено особым способом – принципом верификации. Однако вскоре стало очевидным, что такой прямой верификационизм невозможен в тех случаях, когда мы имеем дело с событиями прошлого, с общими суждениями и т. д. |
