Глава 11

Временная оценка сложности арифметических

операций

11.1. Литература

1. Н. Коблиц, Курс теории чисел и криптографии, Москва, ТВП, 2001 г, 154 с.

2. В.Н. Крупский, Введение в сложность вчислений, М.: Факториал Пресс, 2006 г, 128 с.

3. Введение в криптографию /Под общей ред. В.В. Ященко, -СПб, Питер, 2001. -288 с.

11.2. Позиционные системы счисления

Числа в разных базах. Разложение неотрицательного целого числа n по основанию (базе) b представляет собой

обозначение для n вида dk−1dk−2 . . . d1d0)b, где di - цифры, т.е. символы целых чисел от 0 до b − 1. Эта запись означает,

что n = dk−1bk−1 + dk−2bk−2 + . . . + d1b + d0. Если цифра первого разряда отлична от нуля, то число n называют

k−разрядным b−ичным числом. Любое целое число от bk−1 до bk − 1 является k− разрядным по основанию b.

Дробные числа также можно разлагать по любому основанию, т.е. представлять в виде dk−1dk−2 . . . d1d0, d−1d−2 . . .)b).

11.3. Примеры представления чисел в различных системах счисления

106 = (11110100001001000000)2 = (11333311)7 = (CEXHO)26.

3.1415926 . . . = (11, 001001000011111 . . .)7 = (D, DRS . . .)26

Деление продемонстрируем на следующих примерах: разделим (11001001)2 на (100111)2 и (HAP P Y )26 на (SAD)26

11 0010 01 100111

10 0111

101

1011 01

1001 11

110

H AP P Y SAD

G Y BE KD

COLY

CCAJ

M LP

11.4. Число разрядов

Как было упомянуто выше, целое число, удовлетворяющее неравенствам bk−1 ≤ n < bk имеет k разрядов по

основанию b. С помощью логарифмов это можно переписать в следующем виде (“[ ]” обозначает целую часть числа):

= [logb n] + 1 =

log n

log b

+1

(здесь и всюду далее log понимается как натуральный логарифм).

11.5. Сложение двоичных k-битных чисел

1 111

111 1000

+ 001 1110

1 001 0110

1. Посмотреть на верхний и нижний биты, а также проверить, имеется ли перенос единицы от сложения младших

разрядов.

2. Если оба бита нулевые, а переноса нет, то в данном разряде суммы записываем нуль и двигаемся дальше.

11.6. Двоичная (битовая) операция)

3. Если либо а) оба бита нулевые и есть перенос, либо б) один бит - нуль, другой - единица и переноса нет, то

записываем единицу и двигаемся дальше.

4. Если либо а) один бит - нуль, другой - единица и есть перенос, либо б) оба бита - единицы и переноса нет, то

записываем нуль в данный разряд, записываем единицу переносов в следующий столбец и двигаемся дальше.

5. Если оба бита - единицы и есть перенос, то в данном разряде суммы записываем единицу, записываем единицу

переносов в следующий столбец и двигаемся дальше.

11.6. Двоичная (битовая) операция)

Однократное выполнение этих шагов называется двоичной (битовой) операцией. Сложение двух k - разрядных

двоичных чисел требует k двоичных операций.

Более сложные задачи так же могут быть разбиты на двоичные (битовые) операции. Время затрачиваемое на

выполнение задачи пропорционально числу двоичных операций. Коэффициент пропорциональности отражает реали-

зационные аспекты.

11.7. Умножение k-разрядного двоичного числа на l-разрядное двоичное

число

1 1101

1101

1 1101

11 1 0100

1 11 0 1

1 0 11 1 1001

Предположим, что мы пользуемся обычным способом умножения k-разрядного двоичного числа n и l-разрядного

двоичного числа m. Мы получаем самое большее l строк (каждый нулевой бит числа m уменьшает это количество

на единицу), где каждая строка содержит копию числа n, сдвинутую влево на некоторое расстояние , т.е. копию,

дополненную нулями справа. Пусть имеется l ≤ l строк. Поскольку мы ограничиваемся двоичными операциями, мы

не можем сложить все строки сразу. Правильнее будет двигаться от старой строки к l -й, складывая каждую строку

с накопившейся суммой верхних строк.

В данном примере 11101 × 1101 после сложения первых двух строк получаем 10010001, сносим вниз последние три

разряда 001 и складываем остальное (т.е. 10010 с n = 11101. И наконец, к сумме 10010 + 11101 = 101111 приписываем

001 и получаем 101111001 сумму l = 3 строк.

Это описание показывает, что задача умножения может быть разложена на l −1 сложений, по k двоичных операций

каждые. Так как l − 1 < l ≤ l, то получаем простую оценку.

T ime(умножение k-разрядного и l-разрядного двоичных чисел) < kl

Здесь и далее T ime(A) обозначает число двоичных операций, необходимых для выполнения процедуры A

11.8. Замечания по оценке сложности умножения

Определим “временную оценку (сложности)” арифметической задачи как верхнюю границу для числа двоичных

операций без учета операций сдвига, копирования, обращения в память и т.п. Заметим, что мы могли бы применить

эту же временную оценку к умножению k-разрядной и l-разрядной двоичных дробей. Единственное отличие состоит

в необходимости правильного определения места для запятой, разделяющей целую и дробную части.

Во-вторых, если мы хотим получить простую и удобную в работе оценку, мы всегда должны предполагать, что

имеем дело с “самым плохим случаем”.

Наконец, наша оценка kl может быть выражена в терминах n и m, если вспомнить приведенную выше формулу

для числа разрядов, из которой следует, что k = [log2 n] + 1 ≤ log n + 1 и l = [log2 m] + 1 ≤ log m + 1.

11.9. Пример оценки числа двоичных операций

Найдём верхнюю границу для числа двоичных операций, необходимых для вычисления n!

Используем простую процедуру. Сначала умножим 2 на 3, затем результат умножим на 4 и так далее. На (j − 1)-

м шаге (j = 2, 3, . . . , n − 1 производится умножение j! на j + 1. Поэтому есть n − 2 шагов, каждый из которых

состоит в умножении частичного произведения j! на очередное целое число. Частичные произведения быстро станут

очень большими. В качестве оценки для числа разрядов частичного произведения в наихудшем случае возьмем число

разрядов последнего произведения, т.е. числа n!.

При определении числа двоичных разрядов в произведении используем тот факт, что это число не превосходит

суммы числа разрядов у сомножителей. Следовательно, произведение n целых k-разрядных чисел имеет не более

43

2 2

11. Временная оценка сложности арифметических операций

nk разрядов. Таким образом, если n - двоичное k−разрядное число (тогда любое меньшее число имеет не больше k

разрядов), то n! имеет самое большое nk разрядов.

Итак, в каждом из n−2 умножений, необходимых при вычислении n!, мы умножаем не более чем k-разрядное целое

число j+1 на не более чем nk-разрядное целое число j!. Это требует самое большое nk2 двоичных операций. Всего таких

умножений n − 2. Поэтому общее число двоичных операций ограничено величиной (n − 2)nk2 = n(n − 2)([log2 n] + 1)2,

что приблизительно равно n2(log2 n)2.

11.10. O-большое

Пусть f (n) и g(n) - функции положительного целочисленного аргумента, принимающие положительные (не обя-

зательно целые) значения при всех n. Скажем, что f (n) = O(g(n)) (или просто f = O(g)), если существует такая

константа C, что f (n) всегда меньше Cg(n). Например, 2n2 + 3n − 3 = O(n2) (действительно, нетрудно показать, что

левая часть меньше 3n2).

Рассмотрим f и g как функции нескольких переменных и не будем обращать внимания на соотношение между

ними при небольших значениях n. Так же, как это делается в теории пределом в анализе, будем рассматривать лишь

большие значения n.

Определение Пусть f (n1, n2, . . . , nr ) и g(n1, n2, . . . , nr ) - две функции, определенные на наборах из r положитель-

ных целых чисел. Предположим, что существуют такие константы B и C, что когда все nj больше B, обе функции

положительны и f (n1, n2, . . . , nr ) < Cg(n1, n2, . . . , nr ). В этом случае говорим, что функция f ограничена функцией

g, и пишем f = O(g).

Заметим, что равенство в обозначении f = O(g) следует, скорее, понимать как неравенство <, а O-большое - как

некоторую мультипликативную константу.

11.11. Важные примеры

· Пусть f (n) произвольные многочлен степени d с положительным старшим коэффициентом. Тогда, как легко

показать, f (n) = O(nd). В более общем случае можно показать, что f = O(g), если f (n)/g(n) имеет конечный

предел при n → ∞

· Если ε - сколь угодно малое положительное число, можно показать, что log n = O(nε) (т.е. при больших n

функция log меньше любой степенной, сколь малой не была бы степень). Это следует из равенства limn→∞ logεn =

0, которое доказывается с помощью правила Лопиталя.

· Если f (n) обозначает число k двоичных разрядов числа n, то, как следует из приведенных выше формул для

k, f (n) = O(log n). Заметим, что такое же соотношение выполнено, если f (n) - число разрядов в разложении n

по произвольному фиксированному основанию b. С другой стороны, если основание b не фиксировано, а может

растя, и f (n, b) - число разрядов в записи по основанию b, то f (n, b) = O log n .

· Имеем T ime(n · m) = O(log n · log m), где в левой части стоит число двоичных операций, требующихся для

умножения n на m

· Для факториала имеем T ime(n!) = O (n log n)2

· Для умножения полиномов имеем

T ime

aixi ·

bj xj = O n1n2((log m)2 + log(min(n1, n2)))

11.12. Использование О-большое в оценке вычислительной сложности

Образно говоря, соотношение f (n) = O(nd) показывает, что функция f растет приблизительно как d-я степень

аргумента. Например, если d = 3, то оно говорит нам, что удвоение аргумента приведёт к увеличению функции

приблизительно в 8 раз.

Соотношение f (n) = O(logd n) показывает, что функция возрастает приблизительно как d-я степень числа двоич-

ных разрядов в n. Это так, потому что с точностью до мультипликативной константы число бит равно приблизительно

logn. Так, например, если f (n) = O(log3 n), то удвоение числа бит в n (что гораздо сильнее увеличивает аргумент,

нежели его удвоение) приведёт к увеличению f (n) приблизительно в 8 раз.

11.13. Полиномиальные алгоритмы

В общем случае, когда оценивается число двоичных операций, требующихся для решения какой-либо задачи, снача-

ла надо определить и выписать подробную процедуру решения задачи. Конкретная пошаговая процедура выполнения

вычислений называется алгоритмом.

Определение Алгоритм для проведения вычислений, определяющихся целыми числами n1, n2, . . . , nr из k1, . . . , kr

бит, соответственно называется полиномиальным по времени алгоритмом, если существуют такие целые числа d1, . . . dr ,

d d

что число двоичных операций при работе этого алгоритма равно O k1 1 , . . . , k2 2 .

Таким образом, обычные арифметические операции дают примеры полиномиальных по времени алгоритмов.

44

log b

n

11.14. Пример оценки сложности алгоритма

11.14. Пример оценки сложности алгоритма

Оценить время, требующееся для перевода числа из k бит в десятичную систему счисления.

Алгоритм перевода следующий. Разделим n на 10 = (1010)2. Остаток от деления - который является одним из

чисел 0, 1, 10, 11, 100, 101, 110, 111, 1000 или 1001 - даст содержимое d0 разряда единиц. Частное от деления возьмем

в вместо n, поделим на (1010)2 и возьмём остаток от этого деление в качестве d1, а частное - в качестве делимого

при следующем делении на (10102. Этот процесс должен повторяться столько раз, сколько десятичных разрядов

содержится в числе n, т.е.

+ 1 = O(k) раз. Тогда процесс будет завершён.

Как много двоичных операций будет сделано? Мы сделали O(k) делений, каждое из них требовало O(4k) операций

(делимое содержит не более k бит, а делитель 4 бита). Но O(4k)

O(k). Поэтому общее число двоичных операций

равно O(k)·O(k) = O(k2). Если желательно выразить оценку в терминах n, а не k, то используя равенство k = O(log n),

можно записать

T ime(перевод n в десятичную СС) = O log2n

11.15. Алгоритм Евклида

Алгоритм Еквлида работает следующим образом. Чтобы найти НОД(a, b), где a > b, сначала делят a на b и

записывают частное q1 и остаток r: a = q1b + r1. Затем производят второе деление: b = q2r1 + r2. Затем делят r1 на r2.

Деление продолжают, каждый раз деля предпоследний остаток на последний, получая новые частное и остаток. Когда

в конце концов получатся остаток, который является делителем предыдущего остатка, то этот последний ненулевой

остаток и есть наибольший общий делитель чисел a и b.

Рассмотрим работу алгоритма на следующем примере: найти НОД(1547, 560).

1547 = 2 · 560 + 427

560 = 1 · 427 + 133

427 = 3 · 133 + 28

133 = 4 · 28 + 21

28 = 1 · 21 + 7.

Так как 7|21, то НОД(1547, 560) = 7.

Алгоритм Евклида всегда даёт наибольший общий делитель за конечное число шагов. Кроме того, для a > b

T ime(нахождение НОД(a, b) по алгоритму Евклида) = O log3 a

45

log 10

log n