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

Числа в разных базах. Разложение неотрицательного целого числа n по основанию (базе) b представляет собой обозначение для), где — цифры, т. е. символы целых чисел от 0 до. Эта запись означает, что. Если цифра первого разряда отлична от нуля, то число n называют k-разрядным b-ичным числом. Любое целое число от до является k-разрядным по основанию b. Дробные числа также можно разлагать по любому основанию, т. е. представлять в виде.

.

При b > 10 принято использовать буквы для выражения цифр, больших девяти.

Пример:

• · .
• · При будем использовать буквы латинского алфавита А-Z для записи цифр 0−25 соответственно. Тогда, тогда как

Число разрядов. Как было упомянуто выше, целое число, удовлетворяющее неравенствам, имеет k разрядов по основанию b. С помощью логарифмов это можно переписать в следующем виде (здесь и всюду далее log понимается как натуральный логарифм log_e.

Двоичные операции. Одним из понятий, используемых для сравнения эффективности алгоритмов, является их сложность. Сложность алгоритмов теории чисел обычно принято измерять количеством арифметических операций (сложений, вычитаний, умножений и делений с остатком), необходимых для выполнения всех действий, предписанных алгоритмом.

Предположим, что оба числа имеют длину в k бит. Если запись одного из чисел короче, ее можно дополнить нужным числом нулей слева. Однократное выполнение побитового сложения называется двоичной (битовой) операцией. Сложение двух k — разрядных двоичных чисел требует k двоичных операций. Время, которое расходует компьютер на решение задачи, по сути дела пропорционально числу двоичных операций. Конечно, константа пропорциональности — число наносекунд, расходуемых на одну двоичную операцию, — зависит от вида компьютера. (Сказанное является упрощением, так как это время может зависеть также от «технических» факторов, например, времени доступа к памяти.) Когда мы говорим об оценке времени работы, подразумевается оценка числа двоичных операций. В этих оценках мы будем пренебрегать временем, расходуемым на запись информации или на логические шаги, отличные от двоичных операций. На практике основное время занимает выполнение именно двоичных операций. Теперь рассмотрим процесс умножения k-разрядного двоичного числа на l-разрядное двоичное число.

Предположим, что мы пользуемся обычным способом умножения k — разрядного двоичного числа n- и l-разрядного двоичного числа m. Мы получаем самое большее l строк (каждый нулевой бит числа m уменьшает это количество на единицу), где каждая строка содержит копию числа n, сдвинутую влево на некоторое расстояние, т. е. копию, дополненную нулями справа. Пусть имеется строк. Поскольку мы ограничиваемся двоичными операциями, мы не можем сложить все строки сразу. Правильнее будет двигаться от второй строки кй, складывая каждую строку с накопившейся суммой верхних строк. На каждом этапе сначала отмечаем, как далеко сдвинуто влево число n в рассматриваемой строке. Сносим вниз крайние правые разряды накопленной суммы верхних строк, а остальную часть записи накопленной суммы складываем с числом n, что требует k двоичных операций. Это описание показывает, что задача умножения может быть разложена на — 1 сложений, по k двоичных операций каждое. Так как, то получаем простую оценку Time (умножение k — разрядного и l — разрядного двоичных чисел) <. Здесь и далее Time (A) обозначает число двоичных операций, необходимых для выполнения процедуры А.

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

и .

O большое. Пусть f (n) и g (n) — функции положительного целочисленного аргумента, принимающие положительные (не обязательно целые) значения при всех n. Скажем, что f (n) = 0(g (n)) (или просто f = O (g)), если существует такая константа С, что f (n) всегда меньше С * g (n).

Определение. Пусть — две функции, определенные на наборах из r положительных целых чисел. Предположим, что существуют такие константы В и С, что, когда все n_j больше В, обе функции положительны. В этом случае говорим, что функция f ограничена функцией g, и пишем f = О (g).