- •Глава 4
- •4.1. Комбинаторные вычисления на конечных множествах
- •4.1.2. Асимптотика
- •Говорят, что при Xx0 f(X) растёт медленнее, чем g(X), или что f(X) "есть о-малое" от g(X).
- •Отсюда, в частности, имеем при n
- •4.1.3. Рекуррентные соотношения
- •Последовательность Фибоначчи асимптотически растёт как
- •4.1.4. Производящие функции
- •4.2. Оценки сложности алгоритмов
- •4.3. Методы повышения эффективности алгоритмов
- •4.3.1. Рекурсия
- •4.3.2. Приём “разделяй и властвуй”
- •4.3.3 Принцип балансировки
- •4.3.4. Динамическое программирование
- •4.3.5. Алгоритмы с возвратом
- •Понимание постановки задачи
- •Составление плана решения
- •Взгляд назад
- •Основные этапы полного построения алгоритма
- •Постановка задачи
- •Временная сложность t(n)
- •Ёмкостная сложность е(n)
- •Заключение
- •Контрольные вопросы. Упражнения
О.Н. Паулин. Основы теории алгоритмов
Глава 4
ПОСтроение и анализ алгоритмов
4.1. Комбинаторные вычисления на конечных множествах
4.1.1. Введение в комбинаторику
Предметом теории комбинаторных алгоритмов, часто называемой комбинаторными вычислениями, являются вычисления на дискретных математических структурах. В этой теории большое внимание уделяется алгоритмическому подходу к решению задач дискретной математики, оптимизации перебора вариантов, сокращению числа рассматриваемых решений.
Область комбинаторных алгоритмов включает в себя задачи, которые требуют подсчёта (оценивания) числа элементов в конечном множестве или перечисления этих элементов в специальном порядке (приложение Б). При этом широко применяется процедура выбора элементов с возвращением и её варианты.
Существуют два вида задач подсчёта. В простом случае задаётся конкретное множество и требуется определить точно число элементов в нём. В общем случае имеется семейство множеств, заданное некоторым параметром, и определяется мощность множества как функция параметра. При этом часто бывает достаточной оценка порядка функции, а иногда требуется только оценка скорости её роста. Например, если мощность подлежащего рассмотрению множества растёт по некоторому параметру экспоненциально, то этого может оказаться достаточно для того, чтобы отказаться от предложенного подхода к изучению проблемы, не занимаясь различными деталями. К этому, более общему, типу проблем применяются процедуры асимптотических разложений, рекуррентных соотношений и производящих функций.
4.1.2. Асимптотика
Асимптота — особая линия (чаще всего прямая), являющаяся предельной для рассматриваемой кривой.
Асимптотика — это искусство оценивания и сравнения скоростей роста функций. Говорят, что при х функция "ведёт себя, какх", или "возрастает с такой же скоростью, как х", и при х0 "ведёт себя, как 1/x". Говорят, что "logx при x0 и любом >0 ведёт себя, как x, и что приn растёт не быстрее, чем nlogn". Такие неточные, но интуитивно ясные утверждения полезны при сравнении функций так же, как и соотношения <, и = при сравнивании чисел.
Определим три основных асимптотических соотношения.
Определение 1. Функция f(x) эквивалентна g(x) при хx0, если и только если =1.
В этом случае говорят, что функция f(x) асимптотически равна функции g(x) или что f(x) растёт с такой же скоростью, как и g(x).
Определение 2. f(x)=o(g(x)) при xx0, если и только если =0.
Говорят, что при Xx0 f(X) растёт медленнее, чем g(X), или что f(X) "есть о-малое" от g(X).
Определение 3. f(x)=О(g(x)) при xx0, если и только если существует константа С такая, что sup=С.
В этом случае говорят, что f(x) растёт не быстрее, чем g(x), или что при xx0 f(x) "есть О-большое" от g(x).
Cоотношение f(x)=g(x)+o(h(x)) при x означает, что f(x)-g(x)=o(h(x)). Аналогично f(x)=g(x)+О(h(x)) означает, что f(x)-g(x)=О(h(x)).
Выражения О() и о() могут использоваться также и в неравенствах. Например, неравенство x+o(x)2x при x0 означает, что для любой функции f(x) такой, что f(x)=o(x), при x имеет место соотношение x+f(x)2x для всех достаточно больших значений х.
Приведём некоторые полезные асимптотические равенства.
Полином асимптотически равен своему старшему члену:
при x; (4.1)
при x; (4.2)
при x и ak0. (4.3)
Суммы степеней целых чисел удовлетворяют соотношению:
при n. (4.4)