Теория алгоритмов. Зюзысов В.М. - 54 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

5 Сложность вычислений
Применение математики во многих приложениях требует, как правило,
использования различных алгоритмов. Для решения многих задач не трудно придумать
комбинаторные алгоритмы, сводящиеся к полному перебору вариантов. Но здесь вступает
в силу различие между математикой и информатикой: в информатике недостаточно
высказать утверждение о существовании некоторого объекта в теории и даже
недостаточно найти конструктивное
доказательство этого факта, т.е. алгоритм. Мы
должны учитывать ограничения, навязываемые нам миром, в котором мы живем:
необходимо, чтобы решение можно было вычислить, используя объем памяти и время,
приемлемые для человека и компьютера.
Если дана задача, как найти для её решения эффективный алгоритм? А если
алгоритм найден, как сравнить его
с другими алгоритмами, решающими ту же задачу? Как
оценить его качество? Вопросы такого рода интересуют и программистов, и тех, кто
занимается теоретическим исследованием вычислений.
Введем в первую очередь некоторые понятия, связанные с асимптотической
оценкой функций.
5.1 Асимптотические обозначения
Введем в первую очередь обозначение, связанное с асимптотической оценкой
функций. Хотя во многих случаях эти обозначения используются неформально, полезно
начать с точных определений [13]. На протяжении этого раздела встречающиеся в тексте
функции отображают целые числа в действительные.
Θ–обозначение
Если f(n) и g(n) – некоторые функции, то запись f(n) = Θ(g(n)) означает, что найдутся
такие c
1
, c
2
> 0 и такое n
0
, что 0 ≤ c
1
g(n) ≤ f(n) ≤ c
2
g(n) для всех n ≥ n
0
.
В этом случае говорят, что g(n) является асимптотически точной оценкой для f(n).
Разумеется, это обозначение следует употреблять с осторожностью: Установив, что
f
1
(n) = Θ(g(n)) и f
2
(n) = Θ(g(n)), не следует заключать, что f
1
(n) = f
2
(n)!
Определение Θ(g(n)) предполагает, что функции f(n) и g(n) асимптотически
неотрицательны, т.е. неотрицательны для достаточно больших значений n. Заметим, что
если f и g строго положительны, то можно исключить n
0
из определения (изменив
константы c
1
и c
2
так, чтобы для малых n неравенство также выполнялось).
Это отношение симметрично: если f(n) = Θ(g(n)), то g(n) = Θ(f(n)).
Пример. Проверим, что (1/2)n
2
–3n = Θ(n
2
). Согласно определению надо указать
положительные константы c
1
, c
2
и число n
0
так, чтобы неравенства
c
1
n
2
≤ n
2
/2 – 3n ≤ c
2
n
2
выполнялось для всех n≥n
0
. Разделим на n
2
:
c
1
≤
n
3
2
1
−
≤ c
2
.
Видно, что для выполнения второго неравенства достаточно положить c
2
= ½. Первое
будет выполнено, если, например, n
0
= 7 и c
1
= 1/14.
Другой пример использования формального определения: покажем, что 6n
3
≠ Θ(n
2
).
В самом деле, пусть найдутся такие c
2
и n
0
, что 6n
3
≤ c
2
n
2
для всех n≥n
0
. Но тогда n ≤ c
2
/6
для всех n≥n
0
– что явно не так.
Отыскивая асимптотически точную оценку для суммы, мы можем отбрасывать
члены меньшего порядка, которые при больших n становятся малыми по сравнению с
основным слагаемым. Заметим также, что коэффициент при старшем члене роли не играет

Страницы