Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
(пі + п2 + 1) ((n2 + l)(log2 т + I)2 + n2(log2(n2m2) + 1)
Tl2(Tl1 + Tl2) / (log m) log 2 I log 2
+ (log Ti2 + 21ogm)
8
ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
делителя), снос разрядов и т.п. Таким образом, наша оценка есть просто (к — I -\- 1)1, что не больше kl.
Пример 8. Найти верхнюю границу для числа двоичных операций, необходимых для вычисления биномиального коэффициента
(«)¦
Решение. Так как Q) = (n ™m), то без потери общности можно предположить, что т ^ п/2. Будем использовать следующую процедуру вычисления (") = п(п — 1)(п - 2) • • • (п — т + 1)/(2 • 3 • • • т). Мы имеем 771-1 умножений и последующие 771-1 делений. Ka-ждый раз максимально возможная величина первого числа при умножении и делении есть п(п — 1)(п - 2) • • • (п - т + 1), а граница для второго числа есть п. Рассуждая аналогично примеру 6, убеждаемся в том, что граница для общего числа двоичных операций есть 2 (т — l)m([log2 n] + I)2, что при больших тип приблизительно рав-но 2m (log2 n) .
Теперь обсудим весьма удобное обозначение для краткой записи временных оценок сложности.
О-большое. Пусть f(n) и д(п) — функции положительного целочисленного аргумента, принимающие положительные (не обязательно целые) значения при всех п. Скажем, что f(n) = 0(д(п)) (или просто / = 0(g)), если существует такая константа С, что f(n) все-
2 2
гда меньше Сд(п). Например, 2п + Зп - 3 = 0(п ) (действительно, нетрудно доказать, что левая часть меньше Зп ).
Поскольку мы хотим использовать обозначение О-большое в более общей ситуации, дадим более широкое определение. Рассмотрим / и д как функции нескольких переменных и не будем обращать внимание на соотношение между ними при небольших значениях п. Так же, как это делается в теории пределов в анализе, будем рассматривать лишь большие значения п.
Определение. Пусть /(пі, п2,.. ¦, пг) и д(п\, n2,..., пТ) — две функции, определенные на наборах из г положительных целых чисел. Предположим, что существуют такие константы В и С, что, когда все rij больше В, обе функции положительны и f{rii, п2,..., пг) < Cg{ni, п2, ¦ ¦ ¦, пг). В этом случае говорим, что функция / ограничена функцией д, и пишем / = 0(g).
Заметим, что равенство в обозначении / = 0(g) следует, скорее, понимать как неравенство <, а О-большое — как некоторую мультипликативную константу.
Пример 9. а) Пусть f(n) — произвольный многочлен степени d с положительным старшим коэффициентом. Тогда, как легко показать, f(n) = 0(nd). В более общем случае можно показать, что
§ 1. ВРЕМЕННЫЕ ОЦЕНКИ СЛОЖНОСТИ
9
/ = 0(g), если f(n)/g(n) имеет конечный предел при п —> оо.
b) Если е — сколь угодно малое положительное число, можно показать, что log n = 0(пє) (т.е. при больших п функция log меньше любой степенной, сколь малой ни была бы степень). Это следует из равенства Hm71^00 = 0, которое доказывается с помощью правила Лопиталя.
c) Если f(n) обозначает число к двоичных разрядов числа п, то, как следует из приведенных выше формул для к, f(n) = O(logn). Заметим, что такое же соотношение выполнено, если f(n) — число разрядов в разложении п по произвольному фиксированному основанию b. С другой стороны, если основание Ь не фиксированно, а может расти, и f(n,b) — число разрядов в записи по основанию Ь, то
d) Имеем Time(n • т) = 0(logn • logm), где в левой части стоит число двоичных операций, требующихся для умножения п на т.
e) В примере 6 можно записать Time(n!) = 0((пlogп) ).
f) В примере 7
Time (^T1CLiX1 ¦ Y^bjxl) = 0 (nin2((logm)2 + log (min (щ, n2)))j ¦
Функции f(n) и _/"(Ti1, n2,..., пг) у нас будут часто обозначать время, которое требуется для решения некоторой арифметической задачи с целым числом п или с набором целых чисел Ti1, п2,..., пг в качестве исходных данных. Мы хотим получить наши оценки в виде достаточно простых функций д(п). При этом желательно, чтобы функции д(п) не давали чрезмерно завышенное представление о времени решения задач (хотя с чисто математической точки зрения замена функции д(п) в соотношении / = 0(g) любой большей функцией корректна).
Образно говоря, соотношение f(n) = 0(nd) показывает, что функция / растет приблизительно как d-я степень аргумента. Например, если d = 3, то оно говорит нам, что удвоение аргумента приведет к увеличению функции приблизительно в 8 раз. Соотношение f(n) = 0(\ogd п) (где logd п означает (logn)d) показывает, что функция возрастает приблизительно как d-я степень числа двоичных разрядов в п. Это так, потому что с точностью до мультипликативной константы число бит равно приблизительно logn (а именно, logn/log2 = l,44271ogn). Так, например, если f(n) — 0(log п), то удвоение числа бит в п (что гораздо сильнее увеличивает аргумент, нежели его удвоение) приводит к увеличению f(n) приблизительно в 8 раз.
10
ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
Заметим, что запись /(n) = 0(1) означает, что функция / ограничена некоторой константой.
Замечание. Как мы видели, при умножении двух чисел приблизительно одинакового размера можно использовать формулу Time (А;-разрядное двоичное число • /с-разрядное двоичное число) = 0(к ). Следует заметить, что было предпринято много усилий по повышению скорости умножения двух /с-разрядных двоичных чисел при больших к. Используя специальные приемы, много более сложные, чем обычный школьный способ умножения, математики смогли придумать процедуру умножения двух целых чисел из к бит, требующую всего 0(к log к log log к) двоичных операций. Это лучше, чем 0(к2). и даже лучше, чем 0(к1+є) при любом сколь угодно малом є > 0. Однако дальше мы будем пользоваться только приведенными выше грубыми оценками для времени, необходимого для умножения.
