Главная
»
Информационные системы
»
Алгоритмизация
»
Основные вопросы анализа алгоритмов. Понятие алгоритмической сложности.
Основные вопросы анализа алгоритмов. Понятие алгоритмической сложности.
Основные вопросы анализа алгоритмов – это доказательство корректности алгоритма и оценка времени его работы. Вместе с распространением информационных технологий увеличился риск программных сбоев. Одним из способов избежания ошибок в алгоритмах и их реализациях служат доказательства корректности систем математическими средствами. Использование математического аппарата для анализа алгоритмов и их реализаций называют формальными методами. Доказательство корректности программ позволяет выявлять их свойства по отношению ко всему диапазону входных данных. Для этого понятие корректности было разделено на два типа:
- частичная корректность — программа дает правильный результат для тех случаев, когда она завершается.
- полная корректность — программа завершает работу и выдает правильный результат для всех элементов из диапазона входных данных.
Во время доказательства корректности сравнивают текст программы со спецификацией желаемого соотношения входных-выходных данных. Распространенным критерием оценки алгоритмов является время работы и порядок роста продолжительности работы в зависимости от объема входных данных. Для каждой конкретной задачи составляют некоторое число, которое называют ее размером. Время, которое тратит алгоритм как функция от размера задачи n, называют временной сложностью этого алгоритма T(n). Время, которое тратит алгоритм как функция от размера задачи n, называют временной сложностью этого алгоритма T(n). Асимптотику поведения этой функции при увеличении размера задачи называют асимптотичной временной сложностью. Именно асимптотическая сложность определяет размер задач, которые алгоритм способен обработать. Например, если алгоритм обрабатывает входные данные размером n за время cn², где c — некоторая константа, то говорят, что временная сложность такого алгоритма O(n²). Часто, во время разработки алгоритма пытаются уменьшить асимптотическую временную сложность для наихудших случаев. На практике же бывают случаи, когда достаточным является алгоритм, который «обычно» работает быстро. В следующей таблице приведены распространенные асимптотические сложности с комментариями:
Сложность | Комментарий | Примеры |
O(1) | Устойчивое время работы не зависит от размера задачи | Ожидаемое время поиска в в хеш-таблице |
O(log log n) | Очень медленный рост необходимого времени | Ожидаемое время работы интерполирующего поиска n элементов |
O(log n) | Логарифмический рост — удвоение размера задачи увеличивает время работы на постоянную величину | Вычисление xn; Двоичный поиск в массиве из n элементов |
O(n) | Линейный рост — удвоение размера задачи удвоит и необходимое время | Сложение/вычитание чисел из n цифр; Линейный поиск в массиве из n элементов |
O(n log n) | Линеаритмичный рост — удвоение размера задачи увеличит необходимое время чуть более чем вдвое | Сортировка слиянием или кучей n элементов; нижняя граница сортировки сопоставлением n элементов |
O(n²) | Квадратичный рост — удвоение размера задачи увеличивает необходимое время в четыре раза | Элементарные алгоритмы сортировки |
O(n³) | Кубичный рост — удвоение размера задачи увеличивает необходимое время в восемь раз | Обычное умножение матриц |
O(cn) | Экспоненциальный рост — увеличение размера задачи на 1 приводит к c-кратному увеличению необходимого времени; удвоение размера задачи увеличивает необходимое время в квадрат | Некоторые задачи коммивояжёра, алгоритмы поиска полным перебором |
Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.