Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Глущенко А.В., Кудрина Е.А., Половинко А.С.
Сложность основных алгоритмов.
Оценка сложности арифметических операций.
|
[1] Оглавление [2] Позиционные системы с произвольным основанием. [3] Сложность алгоритма(пример -подсчета достаточного количества операций). [4] Сложность арифметических операций. [5] Оценки функции сложности. [6] Арифметические операции с целыми числами и их сложность [6.1] Двоичные операции. [6.2] О-большое. [6.3] Теорема (О сравнении операций) [7] Список литературы |
Опр. Системой счисления называется совокупность приемов наименования и записи чисел. В любой системе счисления для представления чисел выбираются некоторые символы (их называют цифрами), а остальные числа получаются в результате каких-либо операций над цифрами данной системы счисления.
Опр. Система называется позиционной, если значение каждой цифры (ее вес) изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число.
Опр. Число единиц какого-либо разряда, объединяемых в единицу более старшего разряда, называют основанием позиционной системы счисления. Если количество таких цифр равно P, то система счисления называется P-ичной. Основание системы счисления совпадает с количеством цифр, используемых для записи чисел в этой системе счисления.
Теорема. Пусть p > 1- натуральное число. Тогда для любого nN существует n0,n1,…,nS такие что имеет место равенство (1), где n0,n1,…,nS принимают значения 0,1,…,p-1.
Доказательство. Пусть n=1, для него есть привычная запись: n0=1, ni=0. Предположим что, существуют числа не имеющие вида (1). Тогда среди таких чисел существует наименьшее число k, причем k1, а значит.
Так как , то для k-1 запись вида (1):. Получаем, что , вид типа (1) для k. Наше предположение не верно, теорема доказана.
Единственность. Из записи вида (1) следует что остаток от деления n на p есть n0, где n0 определенно однозначно. Из выражения 1, получаем, что n1 однозначно определенно как остаток от деления на p. И так далее.
Обозначение записи числа в позиционной системе счисления с основанием p. (3), где p основание данной системы счисления., а сама система счисления называется p-ичной.
Замечание. Из Теоремы следует способ нахождения вида (3) любого числа. Алгоритм получается следующий:
- делим на p получаем остаток и неполное частное .
- делим неполное частное снова на, получаем следующий остаток, и т.д.
Под сложностью алгоритма понимается количество выполняемых им арифметических операций (сложение, вычитание, умножение, деление). Это определение не учитывает величину чисел участвующих в вычислениях. Ясно, что перемножить два 100-значных числа сложнее чем два однозначных, хотя при этом выполняется лишь одна математическая операция.
Поэтому учитывают еще и величину чисел, сводя рассмотрение вопроса к битовым операциям, т.е оценивая количество необходимых операций с 0 и 1 в двоичной записи. Сложность алгоритма представляется функцией от длины входа, т.е от функции количества битов N, требуемых для записи входных данных f(N).
Вычислительная сложность алгоритма определяется двумя параметрами: T - временная сложность, S пространственная (требование к памяти).
Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив кару города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10Гб памяти.
Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти
Величина O - это есть порядок вычислительной сложности, это член разложения функции сложности в ряд быстрее всех растущий с ростом .
Пример:
Алгоритм называется:
Постоянным, если его сложность не зависит от n
Линейным, если его временная сложность O(n)
Полиномиальным, если его временная сложность O(nm), m=const
Экспоненциальным, если O(tf(N)), где t=const>1, f(n) - полиномиальная функция от n.
сравнений арифметических операций по трудоемкости.
Лемма: Пусть nN , mR - некоторое кольцо.
Для вычисления степени достаточно не более 2[log2 n] умножений.
Доказательство: Пусть 2S n 2S+1, s=[log2 n]
Запишем n в двоичной системе счисления:
Теперь вынесем степени 1,m,m2,…,. Всего S операций. Затем перемножаем степени , их не более S. В итоге получаем, что для вычисления нужно произвести .
Алгоритм решения вычислительной задачи представляет собой некоторую процедуру, выполняемую над набором данных, т.е. с некоторой информацией, записанной в цифровом виде в виде знаков некоторой системы счисления.
В процессе переработки информации приходится выполнять арифметические действия.
В связи с этим возникает задача выбора наиболее эффективных способов решения, выбора эффективных алгоритмов.
Для изучения алгоритма прибегают к оценке его сложности. Оценить сложность - значит сосчитать с достаточной точностью число элементарных операций, необходимых для его выполнения при фиксированных данных.
Для простоты будем считать, что числа заданы в двоичной системе счисления.
Пусть число n є N в двоичной записи имеет число цифр S+1, т.е.
n = n0+ n1*2+ n2*22 + …+ ns*2s ; , где ns = 1
Значит 2s ≤ n < 2s+1 ⇒ S ≤ log2 n < S+1
Иногда вводят как обозначение log N – длина записи числа N.
В качестве оценки сложности алгоритма обычно выбирается время его работы. (max время для всех наборов данных).
Несмотря на то, что функция временной сложности алгоритма в некоторых случаях может быть определена точно, в большинстве случаев искать точное её значение бессмысленно. Дело в том, что во-первых, точное значение временной сложности зависит от определения элементарных операций (например, сложность можно измерять в количестве арифметических операций, битовых операций или операций на машине Тьюринга), а во-вторых, при увеличении размера входных данных вклад постоянных множителей и слагаемых низших порядков, фигурирующих в выражении для точного времени работы, становится крайне незначительным.
Опр. Порядком роста функции f в точке z0 называется некоторое число α ≥ 0 такое, что для некоторой окрестности U0 существует такое число M > 0, что для произвольной точки z ϵ U0 выполняется неравенство
Рассмотрение входных данных большого размера и оценка порядка роста времени работы алгоритма приводят к понятию асимптотической сложности алгоритма. При этом алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных, за исключением лишь, возможно, данных малого размера. Для записи асимптотической сложности алгоритмов используются асимптотические обозначения:
|
Обозначение |
Интуитивное объяснение |
Определение |
|
f ограничена сверху функцией g (с точностью до постоянного множителя) асимптотически |
Или |
|
|
f ограничена снизу функцией g асимптотически |
||
|
f ограничена снизу и сверху функцией g асимптотически |
< |
|
|
g доминирует над f асимптотически |
||
|
f доминирует над g асимптотически |
||
|
f эквивалентна п асимптотически |
Примеры
1.«Пропылесосить ковер» требует время, линейно зависящее от его площади , то есть на ковер, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз, объем работы увеличивается строго пропорционально в сто тысяч раз, и т. п.
2.«Найти имя в телефонной книге» требует всего лишь время, логарифмически зависящее от количества записей , так как открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге, толщиной в 1000 страниц, любое имя находится не больше чем за раз (открываний книги). При увеличении объема страниц до ста тысяч, проблема все еще решается за заходов.
данные – множество чисел, которые в некоторых системах счисления имеют длину ≤ n
Тогда сложность алгоритма оценивается некоторой функцией , т.е. зависящей от n.
даны два алгоритма с и – функции сложности
, т.е.
в таком виде обычно получают оценки сложности алгоритмов.
При оценке сложности вычислений стремятся свести задачу к подзадачам меньшей размерности и получить неравенство типа:
, а, в, с, d – const ≥0
меньшей размерности м.б. алгоритм известного типа, т.е. с уже известной оценкой
Предположим, что функция обладает дополнительными условиями:
а)
б)
Лемма 1. Если ƒ(n) и g(n) удовлетворяют а) и б), и при некоторых const выполняется:
, то
Доказательство: из условия б) следует, что
Разделив обе части неравенства на a 0 получим ⇒
по a)
, т.е.
Лемма 2. Если при некоторой const a , c, d > 0 удовлетворяет условиям:
при n > 1, то
Доказательство для случая n = at:
по 2)
1) a > c
2) a = c
3) a < c
Сложение и умножение. Начнем с очень простой арифметиче ской задачи сложения двух двоичных целых чисел, например,
Предположим, что оба числа имеют длину в к бит. Если запись одного из чисел короче, ее можно дополнить нужным числом нулей слева.
Детально проанализируем всю процедуру сложения. При сложе нии необходимо к раз повторить следующие шаги.
Посмотреть на верхний и нижний биты, а также проверить, имеется ли перенос единицы от сложения младших разрядов.
Если оба бита нулевые, а переноса нет, то в данном разряде суммы записываем нуль и двигаемся дальше.
Если либо а) оба бита нулевые и есть перенос, либо б) один бит — нуль, другой — единица и переноса нет, то записываем единицу и двигаемся дальше.
Если либо а) один бит — нуль, другой — единица и есть пе ренос, либо б) оба бита — единицы и переноса нет, то записываем нуль в данный разряд, записываем единицу переносов в следующий столбец и двигаемся дальше.
Если оба бита — единицы и есть перенос, то в данном разряде суммы записываем единицу, записываем единицу переносов в следую щий столбец и двигаемся дальше.
Однократное выполнение этих шагов называется двоичной (бито вой) операцией. Сложение двух k-разрядных двоичных чисел требу ет к двоичных операций. Мы увидим ниже, что и более сложные зада чи тоже могут быть разбиты на двоичные операции. Время, которое расходует компьютер на решение задачи, по сути дела пропорциональ но числу двоичных операций. Конечно, константа пропорционально сти — число наносекунд, расходуемых на одну двоичную операцию, — зависит от вида компьютера. (Сказанное является упрощением, так как это время может зависеть также от «технических» факторов, на пример, времени доступа к памяти.) Когда мы говорим об оценке времени работы, подразумевается оценка числа двоичных операций. В этих оценках мы будем пренебрегать временем, расходуемым на запись информации или на логические шаги, отличные от двоичных операций.
Теперь рассмотрим процесс умножения k-разрядного двоичного числа на l-разрядное двоичное число. Например,
Предположим, что мы пользуемся обычным способом умножения k-разрядного двоичного числа п и l-разрядного двоичного числа т. Мы получаем самое большее l строк (каждый нулевой бит числа m уменьшает это количество на единицу), где каждая строка содержит копию числа n, сдвинутую влево на некоторое расстояние, т. е. копию, дополненную нулями справа. Пусть имеется l1 ≤ l строк. Посколь ку мы ограничиваемся двоичными операциями, мы не можем сложить все строки сразу. Правильнее будет двигаться от второй строки к l1-й, складывая каждую строку с накопившейся суммой верхних строк. На каждом этапе сначала отмечаем, как далеко сдвинуто влево число n в рассматриваемой строке. Сносим вниз крайние правые разряды на копленной суммы верхних строк, а остальную часть записи накоплен ной суммы складываем (описанным выше способом) с числом n, что требует к двоичных операций. В примере выше 11101×1101 после сложения первых двух строк получаем 10010001, сносим вниз последние три разряда 001 и складываем остальное (т.е. 10010) с n = 11101. И наконец, к сумме 10010+ 11101 = 101111 приписываем 001 и полу чаем 101111001 — сумму l1= 3 строк.
Это описание показывает, что задача умножения может быть раз ложена на l1-1 сложений, по к двоичных операций каждое. Так как l1 -1 <l ≤ l, то получаем простую оценку
Time (умножение k-разрядного и l-разрядного двоичных чисел) < kl.
Здесь и далее Time (A) обозначает число двоичных операций, необхо димых для выполнения процедуры А.
Замечания. Во-первых, как упоминалось выше, мы подсчитали только число дво ичных операций. Мы пренебрегли временем на сдвиг числа n вле во и временем на снос крайних правых разрядов накопленной суммы. На практике операции сдвига и копирования являются быстрыми по сравнению с большим числом производимых двоичных операций, так что можно без опаски проигнорировать их. Другими словами, мы определим «временную оценку (сложности)» арифметической задачи как верхнюю границу для числа двоичных операций без учета опера ций сдвига, копирования, обращения в память и т.п. Мы могли бы применить эту же временную оценку к умножению k-разрядной и l-разрядной двоичных дробей. Единственное отличие со стоит в необходимости правильного определения места для запятой, разделяющей целую и дробную части.
Во-вторых, если мы хотим получить простую и удобную в ра боте оценку, мы всегда должны предполагать, что имеем дело с «са мым плохим случаем». Например, если двоичное разложение числа m имеет много нулей, то l1 будет значительно меньше l. Поэтому мож но использовать оценку Time (умножение k-разрядного и l-разрядного двоичных чисел) <k (k-число единиц в двоичном разложении m). Од нако обычно вместо такого уточнения (понижения) нашей временной оценки удобнее пользоваться простой равномерной оценкой, зависящей лишь от длины записи n и m, а не от конкретных значений битов.
Как частный случай, имеем оценку:
Time (умножение двух k-разрядных двоичных чисел) < k2.
Наконец, наша оценка kl может быть выражена в терминах n и m, если вспомнить приведенную выше формулу для числа разрядов, из которой следует, что и
Пример 1. Найти верхнюю границу для числа двоичных опе раций, необходимых для вычисления n!
Решение. Используем следующую процедуру. Сначала умно жим 2 на 3, затем результат умножим на 4, новый результат умножим на 5 и т. д., пока не получим n!. На (j - 1)-м шаге (j = 2, 3,..., п — 1) производится умножение j! на ( j +1). Поэтому есть п-2 шагов, ка ждый из которых состоит в умножении частичного произведения j! на очередное целое число. Частичные произведения быстро станут очень большими. В качестве оценки для числа разрядов частичного произведения в наихудшем случае возьмем число разрядов последнего произведения, т.е. числа n!
При определении числа двоичных разрядов в произведении мы используем тот факт, что это число не превосходит суммы числа раз рядов у сомножителей. Следо вательно, произведение п целых k-разрядных чисел имеет не более пк разрядов. Таким образом, если n - двоичное k-разрядное число (то гда любое меньшее число имеет не больше к разрядов), то п! имеет самое большее пк разрядов.
Итак, в каждом из n-2 умножений, необходимых при вычисле нии п!, мы умножаем не более чем k-разрядное целое число j + 1 на не более чем nk-разрядное целое число j!. Это требует самое большее пк двоичных операций. Всего таких умножений п-2. Поэтому общее число двоичных операций ограничено величиной
, что приблизительно равно
Вычитание и деление. Существуют две другие арифметические операции — вычитание и деле ние — имеют те же самые оценки временной сложности, что сложение и умножение соответственно: Time (вычитание к-разрядного двоич ного числа из l-разрядного) ≤ max (k,l), Time (деление k-разрядного двоичного числа на l-разрядное) ≤ kl. Более точно, для описания вы читания надо расширить круг двоичных операций, включив в него операцию вычитания нуля или единицы из других нуля или единицы, возможно, с займом единицы из старшего разряда (см. пример 2).
Анализируя деление в двоичной системе. Пусть к ≥ l (если к < l деление тривиально, т.е. частное равно нулю, а все делимое образу ет остаток). Нахождение частного и остатка требует самое большее k-l+1вычитаний. Каждое вычитание требует l или l + 1 двоичных операций, но в последнем случае в самом левом разряде разности бу дет стоять нуль, поэтому можно опустить одну двоичную операцию (считая, что это скорее операция «по учету данных», а не вычисле ние). Подобным образом мы игнорируем и другие технические детали, например, сравнение двоичных целых чисел (при определении мини мального числа разрядов делимого, которые образуют число, большее делителя), снос разрядов и т.п. Таким образом, наша оценка есть просто (k-l+1)l , что не больше kl.
Пример 2. Найти верхнюю границу для числа двоичных опе раций, необходимых для вычисления биномиального коэффициента
Решение. Так как , то без потери общности мож но предположить, что . Будем использовать следующую про цедуру вычисления . Мы имеем m-1 умножений и последующие m-1 делений. Ка ждый раз максимально возможная величина первого числа при умно жении и делении есть, а граница для второго числа есть п. Рассуждая аналогично примеру 1, убежда емся в том, что граница для общего числа двоичных операций есть , что при больших n и m приблизительно равно .
Теперь обсудим весьма удобное обозначение для краткой записи временных оценок сложности. (А.В.Черемушкин, 2002)
Определение. Пусть и -две функции, определенные на наборах из r положительных целых чи сел. Предположим, что существуют такие константы В и С, что, ко гда все nj больше B, обе функции положительны и В этом случае говорим, что функция f ограничена функцией g, и пишем f = 0(g).
Заметим, что равенство в обозначении f = 0(g) следует, скорее, понимать как неравенство <, а О-большое — как некоторую мульти пликативную константу.
Пример 3. а) Пусть f(n) - произвольный многочлен степе ни d с положительным старшим коэффициентом. Тогда, как легко показать, f(n)= O(nd). В более общем случае можно показать, что f = O(g), если f (n)/g(n) имеет конечный предел при n→∞.
В примере 1 можно записать Time(n!) = O((nlogn)2).
Функции f (n) и у нас будут часто обозначать вре мя, которое требуется для решения некоторой арифметической задачи с целым числом п или с набором целых чисел в качестве исходных данных. Мы хотим получить наши оценки в виде достаточ но простых функций g(п). При этом желательно, чтобы функции g(n) не давали чрезмерно завышенное представление о времени решения за дач (хотя с чисто математической точки зрения замена функции g(п) в соотношении f=O(g) любой большей функцией корректна).
Образно говоря, соотношение f(n)=O(nd) показывает, что функ ция f растет приблизительно как d-я степень аргумента. Напри мер, если d=3, то оно говорит нам, что удвоение аргумента при ведет к увеличению функции приблизительно в 8 раз. Соотноше ние (где означает ) показывает, что функция возрастает приблизительно как d-я степень числа двоичных разрядов в п. Это так, потому что с точностью до мультиплика тивной константы число бит равно приблизительно logn (а именно,). Так, например, если , то удвоение числа бит в n (что гораздо сильнее увеличивает аргумент, нежели его удвоение) приводит к увеличению f(n) приблизительно в 8 раз.
Заметим, что запись означает, что функция f огра ничена некоторой константой.
В общем случае, когда оценивается число двоичных операций, требующихся для решения какой-либо задачи, сначала надо опреде лить и выписать подробную процедуру решения задачи. Конкретная пошаговая процедура выполнения вычислений называется алгорит мом. Конечно, может существовать много разных алгоритмов, вы полняющих одну и ту же работу. Можно воспользоваться тем из них, который попроще в записи, или тем, который быстрее работает, или выбрать какой-то компромисс между простотой и быстродействием. Использованный выше алгоритм умножения n на m далек от самого быстрого из известных. Но вместе с этим он много быстрее метода повторного сложения (m-кратного сложения числа n с собой).
Пример 4. Оценить время, требующееся для перевода числа из k бит в десятичную систему счисления.
Решение. Пусть п - целое из к бит, записанное в двоич ной системе счисления. Алгоритм перевода следующий. Разделим n на 10 = (1010)2. Остаток от деления — который является одним из чисел 0, 1, 10, 11, 100, 101, 110, 111, 1000 или 1001 — даст содержи мое d0 разряда единиц. Частное от деления возьмем вместо n, поде лим на (1010)2 и возьмем остаток от этого деления в качестве dl а частное — в качестве делимого при следующем делении на (1010)2. Этот процесс должен повторяться столько раз, сколько десятичных разрядов содержится в числе n, т.е. раз. То гда процесс будет завершен. Как много двоичных операций будет сделано? Мы сделали О (к) делений, каждое из них требовало O(4к) операций (делимое содержит не более к бит, а делитель (1010)2 - 4 бита). Но О(4к) эквивалентно О(к) (постоянный множитель несуществен в обозначении О-большое). Поэтому общее число двоичных операций равно О(к)×О(к)=O(). Если желатель но выразить оценку в терминах n, а не k, то, используя равенство, можно записать
Time (перевод n в десятичную систему счисления) = О (log2n).
Введем понятия:
M(n)– сложность операции умножения 2-х n разрядных чисел.
D(n)– сложность операции деления с остатком 2n разрядное на n разрядное.
S(n)– сложность операции возведения в квадрат n разрядного числа.
R(n)– сложность операции обращение n разрядного числа(под обратным к n разрядному числу N понимается дробь, полученная из отбрасыванием лишних знаков так, чтобы получилось n разрядное число ).
Теорема. Пусть функции сложности удовлетворяют следующим условиям:
a)f(n)≥n; и b)kf(n)≤f(kn)
Тогда, если M(n),D(n),S(n),R(n) удовлетворяют а) и б), то M(n)≈D(n)≈S(n)≈R(n).
Доказательство:
1)M(n)S(n), так как в силу тождества справедлива оценка M(n)≤3S(n)+4(n),
где 3S(n) - 3 возведения в квадрат, а 4(n)-четыре сложения. M(n) =O(S(n)) Делению на два соответствует операция сдвига.
2)S(n)R(n), т.к. в силу равенства получаем оценку: S(n)≤3R(n)+2n, где 3R(n) - 3 обращения в квадрат, а 2n - два сложения.
Замечание. Это верно только для точных значений , для приблизительных значений и дополнительной оценки смотреть специальную литературу.
3) :
Для доказательства воспользуемся итерационным методом Ньютона для нахождения обратного. Он заключается в вычислении последовательности итераций x(0),x(1),…,x(i),… по формуле: x(i+1)=2x(i)-Nx(i)2 . Данная последовательность действительно сходиться к , т.к. если x(i)= (1-δ), то
Поэтому при выборе начального значения x(0) так, что <(а это легко сделать по двум значащим разрядам N),мы получаем последовательность, в которой каждый раз число правильно вычисленных знаков после запятой удваивается. Благодаря этому мы можем теперь просто заменить нулями те знаки, которым нельзя доверять при данной итерации, и, постоянно удваивая число правильных знаков, через log n шагов получим нужное количество знаков. Отсюда вытекает оценка: (по лемме1).
4) : из равенства
5)– очевидно
По свойству транзитивности, получаем, что включение является замкнутым. .
Метод Карацубы для оценки сложности операции умножения.
Суть метода заключается в рекурсивном повторении шага :
Пусть А и В – два n-разрядных числа. Разобьем их на два слагаемых (для простоты считаем, что)
Тогда
Таким образом, для вычисления произведения двух n-разрядных чисел нужно выполнить три умножения n/2-разрядных чисел и некоторое количество сложений, вычитаний и переносов. Поэтому для сложности данного алгоритма умножения справедлива оценка
Откуда по Лемме 2 где
Пример: умножим два числа 1101 и 1011 с помощью метода Карацубы.
Воспользовавшись тождеством
представим четырехзначные числа A и B в виде
и , где– двузначные числа. Тогда
.
Видно, что достаточно произвести всего три умножения двузначных чисел, ,, на каждое из которых затратили не больше четырех элементарных умножений, т.е. всего затратим 12 умножений вместо 16 (и некоторое количество сложений). В данном случае: a1=11, a0=1, b1=10, b0=11, откуда
11011011=(10211+1)(10210+11)=(104+102)1110+102101+(102+1)111=1113111
(Н.Коблиц., 2001)
А.В.Черемушкин Лекции по арифметическим алгоритмам в криптографии. [Книга]. - Москва : МЦНМО, 2002. - стр. 104.
Н.Коблиц. КУРС ТЕОРИИ ЧИСЕЛ И КРИПТОГРАФИИ. [Книга]. - Москва : Научное изд-во ТВП, 2001. - стр. 254.