Тема 2.4. 4. Оценка сложности алгоритма:
классификация, классы алгоритмов, неразрешимые задачи
Сложность алгоритма помогает оценить затраты на его реализацию и определяется вычислительными мощностями, необходимыми для его выполнения.
Она часто измеряется двумя параметрами:
Сложность представляется как функция f(n), где n - размер входных данных. Чаще всего под размером понимают число обрабатываемых элементов (размер массива данных).
Определим f(n) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций (сложения, сравнения и т.д.), которые должен выполнить алгоритм.
Определим асимптотическую сложность алгоритма.
Если алгоритм обрабатывает входную последовательность размера n за вре-мя cn2, то говорят, что временная сложность этого алгоритма - (n2)
Найдутся такие константы c1; c2 > 0 и такое число n0, что c1n2 6 f(n) 6 c2n2 при всех n > n0.
Вообще, если g(n) - некоторая функция, то запись f(n) = (g(n)) означает, что найдутся такие c1; c2 > 0 и такое n0, что c1g(n) 6 f(n) 6 c2g(n) при всех n > n0.
Запись f(n) = (g(n)) включает в себя две оценки - верхнюю и нижнюю. Их можно разделить (в данном случае нас больше интересует верхняя оценка). Говорят, что f(n) = O(g(n)), если найдется такая константа с > 0 и такое число n0, что 0 6 f(n) 6 cg(n) для всех n > n0.
Также существуют определения:
Функция f(n) является O[g(n)] (о-большое) для больших n, если:
lim f(n) = const 6= 0
n!1 g(n)
Функция f(n) является o[g(n)] (о-малое) для больших n, если:
lim f(n) = 0
n!1 g(n)
Она часто измеряется двумя параметрами:
T - временная сложность
S - пространственная сложность
Сложность представляется как функция f(n), где n - размер входных данных. Чаще всего под размером понимают число обрабатываемых элементов (размер массива данных).
Определим f(n) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций (сложения, сравнения и т.д.), которые должен выполнить алгоритм.
Определим асимптотическую сложность алгоритма.
Если алгоритм обрабатывает входную последовательность размера n за вре-мя cn2, то говорят, что временная сложность этого алгоритма - (n2)
Найдутся такие константы c1; c2 > 0 и такое число n0, что c1n2 6 f(n) 6 c2n2 при всех n > n0.
Вообще, если g(n) - некоторая функция, то запись f(n) = (g(n)) означает, что найдутся такие c1; c2 > 0 и такое n0, что c1g(n) 6 f(n) 6 c2g(n) при всех n > n0.
Запись f(n) = (g(n)) включает в себя две оценки - верхнюю и нижнюю. Их можно разделить (в данном случае нас больше интересует верхняя оценка). Говорят, что f(n) = O(g(n)), если найдется такая константа с > 0 и такое число n0, что 0 6 f(n) 6 cg(n) для всех n > n0.
Также существуют определения:
Функция f(n) является O[g(n)] (о-большое) для больших n, если:
lim f(n) = const 6= 0
n!1 g(n)
Функция f(n) является o[g(n)] (о-малое) для больших n, если:
lim f(n) = 0
n!1 g(n)
Определяя асимптотическую сложность алгоритма, мы отбрасываем члены меньшего порядка суммы, которые при больших n становятся малыми, по сравнению с другими слагаемыми.
Пример
Если временная сложность алгоритма описывается как
T (n) = 4n2 + 7n + 12, то вычислительная сложность определяется, как O(n2).
Запись оценки сложности позволяет увидеть, как объем входных данных влияет на требования ко времени выполнения. Например, если T (n) = O(n), то удвоение входных данных удвоит и время работы алгоритма. Если
T = O(2n), то добавление одного бита к входным данным удвоит время выполнения
Обычно алгоритмы классифицируют в соответствии с их временной сложностью.
Можно выделить следующие их типы:
Постоянный - сложность оценивается как O(1). Логарифмический - сложность оценивается как O(log(n)) Линейный - оценка равна O(n).
С ростом n временная сложность может стать настолько огромной, что это повлияет на практическую реализуемость алгоритма. Рассмотрим таблицу, в которой сравнивается время выполнения алгоритмов разных типов при n = 106, при условии, что единицей времени для компьютера является микросекунда (10 6).
Сравнение алгоритмов по сложности
Пример
Если временная сложность алгоритма описывается как
T (n) = 4n2 + 7n + 12, то вычислительная сложность определяется, как O(n2).
Запись оценки сложности позволяет увидеть, как объем входных данных влияет на требования ко времени выполнения. Например, если T (n) = O(n), то удвоение входных данных удвоит и время работы алгоритма. Если
T = O(2n), то добавление одного бита к входным данным удвоит время выполнения
Обычно алгоритмы классифицируют в соответствии с их временной сложностью.
Можно выделить следующие их типы:
Постоянный - сложность оценивается как O(1). Логарифмический - сложность оценивается как O(log(n)) Линейный - оценка равна O(n).
- Квадратный - O(n2)
- Кубический, полиноминальный - O(n3); O(nm).
- Экспоненциальный - O(tp(n)), t- константа, p(n) - некоторая полиномиальная функция.
- Факториальный - O(n!). Обладает наибольшей временной сложностью среди всех известных типов.
- Логарифмическая сложность присуща алгоритмам, которые сводят боль-шую задачу к набору меньших задач, уменьшая на каждом шаге размер задачи на постоянную величину. Например, двоичный поиск в массиве, ко-гда на каждом шаге размер массива сокращается вдвое.
- Линейное время выполнения свойственно тем алгоритмам, в которых осу-ществляется небольшая обработка каждого входного элемента.
- Оценка nlog(n) возникает в тех случаях, когда алгоритм решает задачу, разбивая её на меньшие подзадачи и решая их независимо друг от друга, а затем объединяя решение.
- Квадратичное время выполнения свойственно алгоритмам, обрабатываю-щим все пары элементов данных.
- Кубическое время соответсвует алгоритмам, которые обрабатывают все трой-ки элементов данных.
- Экспоненциальное и факториальное время присуще алгоритмам, которые выполняют перебор всевозможных сочетаний элементов
С ростом n временная сложность может стать настолько огромной, что это повлияет на практическую реализуемость алгоритма. Рассмотрим таблицу, в которой сравнивается время выполнения алгоритмов разных типов при n = 106, при условии, что единицей времени для компьютера является микросекунда (10 6).
Сравнение алгоритмов по сложности
Оценка времени
Часто приходится сталкиваться с показателями времени, выраженных в секундах. В следующей таблице содержится перевод секунд в другие единицы измерения времени
Междисциплинарный курс
Разработка программных модулей
Вы можете оставить отзыв отправив письмо на данную почту
pobeats30@gmail.com
pobeats30@gmail.com
