01 Июл

курс лекций+практика

    Традиционно в программировании понятие сложности алгоритма связано с использованием ресурсов компьютера: насколько много процессорного времени требует программа для своего выполнения, насколько много при этом расходуется память машины? Учет памяти обычно ведется по объему данных и не принимается во внимание память, расходуемая для записи команд программы. Время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой для машин с разной тактовой частотой и с незначительными вариациями в архитектуре.

    Такой подход сложился исторически и ориентируется прежде всего на научные и инженерные приложения теории алгоритмов: объемы данных значительно превышают размеры самой программы, а программа может выполняться несколько часов. Если не считать офисных и бухгалтерских применений вычислительных машин, то производительность и объем памяти компьютера никогда не казались программистам чрезмерными и постоянной задачей является сделать программу работающей хотя бы немного быстрее и попытаться заставить ее работать в стесненных условиях ограниченного поля памяти.

). Это основанные на компьютерах системы, которые управляют процессами в реальном мире или обрабатывают информацию, служащую для принятия оперативных решений. Примерами систем реального времени являются бортовые компьютерные системы космических кораблей, самолетов, других транспортных средств; компьютерные системы, управляющие непрерывным химическим производством, ядерными реакторами; системы противовоздушной обороны, управления огнем и др.

).

наиболее распространенных ЭВМ. Временную сложность будем подсчитывать в исполняемых командах: количество арифметических операций, количество сравнений, пересылок (в зависимости от алгоритма). Емкостная сложность будет определяться количеством скалярных переменных, элементов массивов, элементов записей или просто количеством байт.

 — емкостная сложность.

 зависит не только от вида данных, но и от вида алгоритма или от задачи, которую этот алгоритм решает.

). Программа итеративного решения задачи имеет следующий вид:

: integer): integer;

;

= 1;

= m*i;

= m;

;

.

 нет, имеется лишь зависимость от количества компонент.

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

как с прикладной, так и с теоретической точек зрения.

 — область допустимых значений входных данных (задача с ограничением на временную сложность).

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

    Двойственная задача минимизации емкостной сложности при ограничениях на временную сложность возникает реже в силу архитектурных особенностей современных ЭВМ. Дело в том, что запоминающие устройства разных уровней, входящие в состав машины, построены так, что программе может быть доступна очень большая, практически неограниченная область памяти — виртуальная память. Недостаточное количество основной памяти приводит лишь к некоторому замедлению работы из-за обменов с диском. Если учесть, что в любой момент времени программа работает лишь с двумя-тремя значениями и использование кэша и аппаратного просмотра команд программы вперед позволяет заблаговременно перенести с диска в основную память нужные значения, то можно констатировать, что минимизация емкостной сложности не является первоочередной задачей. Поэтому в дальнейшем будем интересоваться в основном временной сложностью алгоритмов.

    С теоретической точки зрения важным является вопрос: как далеко для данной задачи можно продвигаться по пути совершенствования (уменьшения сложности) алгоритмов ее решения, когда наступает предел, свойственный самой задаче, далее которого попытки совершенствования алгоритмов заведомо не приведут к успеху?

.

 

.

.

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

, не говоря уже о том, что среди выражений равной длины будут выражения разной сложности.

) оценивается количество необходимых операций в худшем случае, т.е. для набора исходных данных, требующих максимального количества операций обработки (сложность для худшего случая — верхняя оценка), и в лучшем случае — для набора, требующего минимального количества операций. Таким образом, получаются верхняя и нижняя оценки сложности алгоритма (рисунок 1).

Рис.1. Зависимость сложности алгоритма от сложности данных

 средней оценки.

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

.

 

алгоритмы.

    С целью анализа алгоритм (программу) удобно представлять управляющим графом (родственное понятие — схема алгоритма).

    Управляющий граф строится следующим образом. Каждому оператору присваивания или вызову процедуры ставится в соответствие вершина графа (точка). Два последовательно записанных оператора (последовательно исполняемых) изображаются вершинами, соединенными стрелкой, указывающей порядок исполнения (рис. 1).

Рис.1. Граф линейного участка

 (рисунок 2).

а

:= b;

Рис.2. Граф условного оператора

, но только разветвление может быть на большее число ветвей и выходящие дуги помечаются соответствующими константами (рис.3).

Рис.3. Граф оператора разветвления

    Операторы цикла (рисунок 4) изображаются в управляющем графе замкнутой последовательностью вершин (циклом).

Рис.4. Графы операторов цикла

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

.

 

.

. Сложность равна сумме весов вершин, принадлежащих линейному участку, и является константой, если на участке нет вершин — вызовов процедур. Если такие вершины есть, то их вес равен функциям сложности соответствующих процедур.

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

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

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

Управляющий граф содержит разветвления

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

 

. Таким образом, имеется две ветви с весом 3+5+1+4+3+4+5+3 = 28 и 3+5+1+6+8+5+3 = 31; сложность равна 31.

 

.

    Для среднего случая, кроме веса ветвей, нужно оценить еще и частоты ветвей. Под частотой ветви понимается отношение числа выполнений программы, при которых исполнялись операторы, принадлежащие данной ветви, к общему числу выполнений программы. Тогда сложность программы будет вычисляться как сумма произведений весов ветвей на их частоты. Если все комбинации исходных данных программы равновероятны, то частоты ветвей можно оценить следующим образом.

 и т. д.

.

Рис.1. Управляющий граф и разбиение области данных

 то сложность программы можно оценить величиной

 — количество ветвей.

 

5 .

 

.

.

.

for

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

 

. Процедура содержит цикл

<тело цикла>,

.

 

. Процедура содержит вложенные циклы:

<тело цикла>;

равновероятны. Тогда среднее значение сложности равно:

.

c: matrix);

, j, k: integer;

1.}

{Цикл 2 и начало тела цикла 1.}

begin

{Начало тела цикла 2.}

3.}

3.}

{Конец тела цикла 2; конец тела цикла 1.}

end

, то ее временная сложность

Тα (n) = n*(сложность тела цикла 1).

    В свою очередь,

сложность тела цикла l = n*(сложность тела цикла 2)

и, следовательно,

* (сложность тела цикла 2)).

    Тело цикла 2 состоит из одного оператора присваивания и цикла 3. Таким образом,

* (1 + n * (сложность тела цикла 3))).

    Тело внутреннего цикла включает умножение, сложение и присваивание (3 операции). Окончательно получаем

2

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

    Следует отметить также, что фактически был проведен рекурсивный процесс оценки функции сложности.

.

 

repeat

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

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

с помощью, например, следующей функции.

( p: integer; x, z0, epsilon: real ): real;

: integer;

, z: real;

begin

:= z0;

repeat

:= z;

= old;

:= y*old;

:= (p — l)*old/p + x/ (p*y);

abs( z — old ) < epsilon;

;

.

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

.

    Рассмотрим сначала случай прямой рекурсии с единственным (вне какого-либо цикла) рекурсивным вызовом в теле процедуры. Примером такого алгоритма является алгоритм Евклида вычисления наибольшего общего делителя.

. Тогда

),

или

).

. Таким образом, имеется система:

c(X, S)

(S)

Это частный случай рекуррентного уравнения. Такие уравнения имеют развитую теорию. В некоторых случаях возможно аналитическое решение. Покажем его применение на примере рекурсивного вычисления факториала:

: integer): integer;

begin

FACTORIAL:= 1

FACTORIAL:= x * FACTORIAL (x-1);

;

Таким образом, система уравнений превращается в

4, Тα(1) = 2.

.

 может быть получена подобным образом, но с использованием рекуррентных неравенств:

(V)+Tc(V,V0),

(V0).

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

среднее (X)),

.

. Рекуррентное уравнение для функции сложности имеет вид

(X) + …+

h (X) + Tc (X, S)

(S).

(X), однако, подчиняющиеся обычно определенным закономерностям. Эти наиболее часто встречающиеся случаи мы сейчас рассмотрим.

. Рекуррентное уравнение для функции сложности имеет вид:

, S),

(S).

.

Рис.1. Ханойская башня

    Задача состоит в следующем.

.

    С алгоритмической точки зрения элементарным шагом является перенос одного диска. В задаче имеется важное ограничение: ни на одной из игл никогда не должно возникать ситуации, при которой диск большего диаметра лежит на диске меньшего диаметра.

 как вспомогательную. Тогда исходная задача может быть разбита на три части:

{Перенести верхние n-1 дисков на с.}

{Перенести один (нижний) диск на b.}

Перенести башню с c на большой диск, уже находящийся на b.}

. Теперь можно написать рекурсивную процедуру:

);

then

begin

);

);

CARRY (n-1, c, b, a)

;

;

. Рекурсивное уравнение примет вид:

Тα (n) = 2Тα (n-1) +2 + h + 1,

Тα (1) = 1 + 0, или

Тα (n) = 2Тa (n-1) + h + 3, Тα (1) = 1.

    Решение этого уравнения может быть получено в виде:

Тα (n) = v 2n + w,

 — параметры, подлежащие определению.

 получаются из предыдущих рекуррентных соотношений:

2 + w = 1

    Итого,

Tα (n) = (2 + h/2) 2n — (h + 3).

    Найденная оценка сложности относится к классу так называемых экспоненциальных функций временной сложности.

    Второй тип рекуррентных уравнений, часто встречающихся в анализе алгоритмов, может быть задан следующими формулами:

,

Тα (1) = l,

 — натуральное число.

.

    Асимптотическое решение уравнений этого типа будет следующим:

если k < m,

), если k = m,

m.

.

числа Фибоначчи. Проведем более детальный ее анализ.

;

Fr := 1

Fr := Fr(n-1) + Fr(n-2);

;

.

.

) уравнения имеют вид:

(X),

X, S),

(S)

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

.

.

GCD (n, m: integer): integer;

GCD := n

m);

;

. Это нелинейное преобразование.

 не является хорошим аргументом функции сложности.

. Иначе остатки можно определить системой равенств:

,

,

,

. . . . .

,

k

. Перенумеруем последовательность остатков с конца:

,

,

,

. . . . .

,

.

 можно записать в виде одного рекуррентного уравнения

(i-2)

.

.

 и является оценкой сложности алгоритма.

 может быть выражено формулой

число

 не превышает по абсолютной величине единицы, то можно написать следующие неравенства:

    Вывод средней оценки сложности алгоритма Евклида приведен в книге Д. Кнута (Т. 2, разд. 4.5.3). Однако, когда оценка худшего случая всего лишь логарифмическая, средняя оценка представляет, в основном, теоретический интерес (в данном случае она тоже логарифмическая, но с меньшим коэффициентом).

. Тогда:

    Она говорит о том, что в 60% случаев алгоритм Евклида будет заканчиваться получением остатка, равного 1; такой остаток мы рассматривали как худший случай при анализе сложности.

.

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

 для разных деревьев могут отличаться функции сложности одной из самых простых операций — вставки нового элемента.

вершин, и вырожденное (линейный список).

 и количество элементарных шагов (таких же, как и для идеального дерева) зависит на этот раз от включаемого элемента. Для определенности рассмотрим дерево, состоящее только из правых поддеревьев (в дерево включались упорядоченные по возрастанию элементы). Различаются три случая:

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

все имеющиеся в дереве элементы предшествуют новому; новый элемент должен стать правым потомком последней (самой правой) вершины, для этого требуется выполнить n элементарных шагов; дерево остается вырожденным;

, элементарных шагов, дерево перестает быть вырожденным.

.

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

;

.

, а количество переходов на единицу меньше.

.

уровня к общему количеству вершин дерева:

    Среднее количество сравнений (математическое ожидание) равно:

, а для вычисления второго слагаемого можно использовать известную формулу:

    Таким образом, после преобразований получаем выражение:

. Следовательно, максимальная и средняя сложность поиска информации в идеальном дереве почти совпадают.

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

 вершинами?

Сколько среди них вырожденных и как часто они возникают?

Сколько среди деревьев идеальных или близких к идеальным, какие последовательности значений их порождают?

    Ответы на эти вопросы важны потому, что если большинство деревьев — вырожденные, то деревья почти не имеют преимуществ перед списками, а недостаток очевиден — для деревьев требуется больше памяти. Если же большинство деревьев близки к идеальным, то дерево как структура данных для хранения информации имеет большое значение и стоит приложить усилия к совершенствованию процедур работы с деревьями (например, чтобы совсем исключить появление вырожденных деревьев).

.

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

 вершин. Под различными деревьями мы понимаем в том числе учет свойства вершины быть левым или правым потомком. Таким образом, симметричные деревья, изоморфные с точки зрения теории графов, являются различными. Например, вырожденные деревья, представляющие собой цепи левых и правых потомков — различны с нашей точки зрения, хотя и изоморфны. Имеет место формула:

которую можно объяснить следующим образом.

 вершинами.

    Приведенное равенство можно использовать для итерационного вычисления количества деревьев, начиная с деревьев, содержащих одну вершину:

= 1,

= 2,

= 5 и т.д.

.

:

Получили уравнение:

(z)

, которое имеет решение:

 имеет вид:

    Таким образом,

.

.

Рис.1. Примеры вырожденных деревьев

Идеальные деревья

. Значит ли это, что плохие деревья встречаются чаще, чем хорошие?

 чисел. Это значительно больше, чем количество:

) и характеризуют частоту появления идеальных деревьев.

-й уровень.

    Другая группа — заполнение дерева сначала левого поддерева, а затем правого и т. д. — непересекающихся групп может быть выделено очень много (две последовательности отличаются, если в них изменен порядок хотя бы двух чисел).

 (рисунок 2).

Рис.2. Идеальное четырехуровневое дерево

    Любая последовательность чисел 1, 2, 3, …, 15 должна начинаться с 8, иначе построить дерево не удастся. Вторым членом последовательности может быть 4 или 12, третьим членом — то из двух чисел, которое не было выбрано в качестве второго члена. Четвертым членом может быть любое из чисел 2, 6, 10, 14, пятым — любое из трех, не выбранных в качестве четвертого и т. д.

    Рассматривая заполнение по уровням, можно заметить, что:

, которое должно стать корнем;

на втором уровне имеется 2 вершины и 2! возможностей выбора второго и третьего элементов последовательности;

на третьем уровне 4 вершины и 4! возможностей выбора четвертого … седьмого элементов последовательности;

заполнении, равно:

)!

 последовательностей (общее количество последовательностей, приводящих к идеальному графу любыми способами, равно 80 — найдено прямым подсчетом). Вырожденных деревьев — 64.

.

 это всегда так, оценим отношение частот их появления; причем частоту появления идеальных деревьев оценим снизу, используя количество последовательностей, строящих дерево по уровням. Чуть менее громоздко формула будет выглядеть, если взять логарифм отношения частот. Факториалы, встречающиеся в формулах, заменим приближенными выражениями по формуле Стирлинга:

    Тогда логарифм отношения частот равен:

    В выводе последней формулы для упрощения выражения некоторые конечные суммы (геометрической прогрессии и др.) заменены бесконечными, что, учитывая быструю сходимость соответствующих рядов, дает относительно небольшую ошибку.

 значение логарифма отношения частот положительно и, следовательно, идеальные деревья встречаются чаще вырожденных. Более того, значение логарифма быстро растет, увеличивая разрыв частот.

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

    Из приведенных выше результатов можно с достаточной степенью уверенности сделать следующий вывод: хорошие деревья получаются в результате включения случайных элементов существенно чаще, чем плохие; поэтому, средние оценки сложности операций поиска и включения вероятнее всего будут логарифмическими.

.

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

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

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

    При включении новой вершины в дерево может (но не обязательно) увеличиться высота одного из поддеревьев. Ситуации может быть три:

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

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

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

    В третьем случае при включении вершины предпринимается перестройка дерева.

.

.

.

.

 уменьшилась на единицу, и дерево стало сбалансированным.

.

 не поднимается).

. Неважно, какому именно. Оба их можно поднять. Преобразование

)

, что надо учитывать при написании списка формальных параметров процедур.

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

.

.

    Одна из задач, которая обычно ставится при разработке алгоритмов и программ — минимизация требуемых программой ресурсов. Особенно это касается системного программного обеспечения: программ операционной системы, трансляторов, систем управления базами данных и знаний и т. д., т.е. программ, имеющих большое количество пользователей и испытывающих как товар, большую конкуренцию на рынке программных средств.

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

, предназначенные для оценки архитектур.

как минимальную из сложностей алгоритмов, решающих эту задачу. Но существует ли алгоритм минимальной сложности (как убедиться, что найденный алгоритм действительно минимальный или, напротив, не минимальный)? Есть ли к чему стремиться? И насколько труден поиск этого минимума? Эти вопросы связаны с нижней оценкой сложности алгоритмов (а не верхней, как в предыдущих шагах).

элементов. Для вычисления любого элемента нужна хотя бы одна операция однопроцессорной машины — два элемента за одну операцию найти нельзя. Таким образом, для минимального алгоритма мы получаем неравенства

2

).

    Имея в виду сказанное, можно отступить от математической традиции и под оптимизацией алгоритмов понимать просто изменение алгоритма или поиск нового с меньшей сложностью.

    Существует несколько самостоятельных аспектов оптимизации программ, из которых выделим два:

оптимизация, связанная с выбором метода построения алгоритма;

оптимизация, связанная с выбором методов представления данных в программе.

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

    Общим руководящим подходом здесь может быть последовательность действий, обратная анализу алгоритмов. При анализе по рекурсивному алгоритму строится уравнение, которое затем решается. При оптимизации реализуется цепочка:

Формула, задающая желаемую сложность ->

Соответствующее уравнение (одно из возможных) ->

Метод разбиения задачи на подзадачи.

.

 раз меньшего размера с уравнением для функции сложности:

, T(1) = b,

.

.

    Сделаем попытку применить рекурсию с использованием известного в теории матриц блочного представления:

.

.

 для хранения промежуточных результатов.

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

(А, В: матрица;

: индекс; n: размер);

X1, X2: матрица;

то

{Вычислить 1-й блок:}

);

, 1, 1, n/2);

, n/2);

{Вычислить 2-й блок:}

/2, 1, 1, n/2);

/2,1,1,n/2);

/2, n/2);

{Вычислить 3-й блок:}

,1,1, n/2);

/2);

, n/2);

{Вычислить 4-й блок:}

/2);

/2,1,1, n/2);

/2, n/2);

конец

{Умножение скаляров.}

конец

.

 было меньше восьми.

предложил вычислять блоки матрицы-произведения следующим образом:

    В этих равенствах только семь умножений матриц, следовательно, рекурсивная процедура содержит в своем теле семь рекурсивных вызовов. Кроме того, имеется 18 аддитивных (сложений и вычитаний) матричных операций, но они не рекурсивны и имеют квадратичную сложность.

классическом алгоритме их четыре) велики. Но с теоретической точки зрения результат очень важен: он помогает продвинуться к пониманию того, какова сложность задачи.

.

 

    Длинные целые числа используются в арифметике высокой точности (Д. Кнут. Т. 2), криптографическом кодировании сообщений (шифровании). При этом длина чисел (т.е. количество цифр в записи числа) может достигать нескольких сотен и более. Арифметические операции (сложение, вычитание, умножение, деление) над длинными числами не могут выполняться компьютером за один шаг. Любая такая операция должна реализовываться специально написанной процедурой.

Представление длинных целых чисел

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

соответствует младшей цифре в записи числа.

Алгоритм умножения 1 (классический)

.

;

; n, m: integer);

;

Место для формирования двух цифр.}

.}

{Подготовка места для результата.}

V.}

{Сначала переноса нет.}

U.}

]*V[j]+W[i+j-1]+C;

{Временное значение очередной цифры.}

{Формирование разряда переноса.}

;

{Старшая цифра частичного произведения.}

;

;

.

Алгоритм умножения 2 (оптимизированный по времени)

.

. То же можно сказать о сложности аддитивных операций.

.

    Но можно немного преобразовать расчетную формулу:

+1)

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

,

, что значительно лучше классического алгоритма.

.

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

, что встречается в некоторых критических приложениях, например, в шифровании информации.

 операция умножения.

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

 умножений. Для других показателей он требует видоизменения.

. Интересно, что для меньшей степени (1023 < 1024) требуется на восемь умножений больше!

.

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

: integer);

: integer;

begin

:= x;

:= NextBit(n);

{В B — первая единица.}

(n);

{Пока не закончилась запись числа n.}

begin

у:= у*у;

у:= у*х;

;

;

 и может быть определена формулой:

.

:

.

    Что общего между рассмотренными методами оптимизации алгоритмов?

    Стандартные алгоритмы решения задач перемножения матриц, длинных чисел, возведения в степень сводили задачу к длинной последовательности однородных подзадач малого размера. Эта последовательность записывалась в виде итеративного алгоритма, складывающего простым (стандартным) образом общее решение из решений независимых малых подзадач. Малые подзадачи отличаются по своей постановке от исходной задачи.

нестандартный, усложненный метод соединения подзадач, позволяющий обойтись меньшим их числом. При этом подзадачи оказываются зависимыми.

.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *