Количество повторений вложенного цикла не зависит от параметра внешнего цикла

Построить функцию сложности итеративного алгоритма умножения двух квадратных матриц А = {a_ij} и B = {b_ij} размера n x n, результатом которого является матрица C = {c_ij}, также размером n x n.

procedure MULTIPLY (n: integer; a, b: matrix; var c: matrix);

var i, j, k: integer;

Begin

for i:= 1 to n do {Цикл 1}

for j:= 1 to n do {Цикл 2 и начало тела цикла 1}

begin

  c [ i, j ]:= 0; {Начало тела цикла 2}

  for k:= 1 to n do {Цикл 3}

   c[i, j]:= c[i, j] + a[i, k] * b[k, j]; {Тело цикла 3}

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

end;

Тип данных matrix определен вне процедуры как двумерный массив. Время доступа к элементам не учитываются при анализе алгоритмов. Прежде всего, выберем параметр V. Простой анализ текста показывает, что за параметр сложности данных можно взять размер n матриц, участвующих в вычислениях. Поскольку процедура представляет собой цикл по переменной i, то ее временная сложность

Т _α (n) = n· T ⁽¹⁾.

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

T ⁽¹⁾ = n· T ^{( 2 )}

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

Т _α (n) = n·(n· T ^{( 2 )}).

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

Т _α (n) = n·(n·(1 + n· T ^{( 3 )})).

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

Т _α (n) = n ·(n ·(1 + n ·3)) = 3 n ³ + n ²

Количество повторений вложенного цикла зависит от параметра внешнего цикла

Введем следующие обозначения:

k - количество повторений внешнего цикла. В примере k=n.

f(k) – функция зависимости количества повторений вложенного цикла от числа повторений внешнего цикла. В примере f(1)=1, f(2)=2, …, f(n)=n.

T⁽¹⁾, T⁽²⁾ - временная сложность тела цикла 1-го (верхнего) уровня и 2-го уровня (вложенного цикла) соответственно. В примере T⁽²⁾ = 2.

a⁽¹⁾ - временная сложность операторов, предшествующих вложенному оператору цикла, в теле цикла верхнего уровня. В примере a⁽¹⁾ = 1.

b⁽¹⁾ - временная сложность операторов, следующих после вложенного оператора цикла, в теле цикла верхнего уровня. В примере b⁽¹⁾ = 2.

T – временная сложность всего алгоритма.

a – временная сложность операторов, предшествующих циклу, в основном алгоритме. В примере a=1.

b – временная сложность операторов, следующих после цикла в основном алгоритме. В примере b=1.

T = a+b+k∙(a⁽¹⁾ +b⁽¹⁾) + T⁽²⁾∙

 

11) Оценка сложности рекурсивных алгоритмов: рекурсия с 1 и многими рекурсивными вызовами, случай косвенной рекурсии.

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

При прямой рекурсии процедура содержит вызов себя в собственном теле, например:

procedure процедура _1

….

if … then процедура _1

….

end;

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

procedure процедура_1

….

… процедура_2

….

end;

procedure процедура_2

….

… процедура_3

….

end;

procedure процедура_3

….

… процедура_1

End;

 

· Для вычисления сложности рекурсивных алгоритмов используется рекуррентное уравнение:

T _a (X)=T _a (f(X))+ T_f(X)+ T_h(X)+ T_с (X,S)

T _a (S)=T_c(S,S)+ T_s(S)

Здесь

T _a(X) – общая сложность рекурсивного алгоритма

T _a(f(X)) – сложность предыдущего уровня рекурсии

T_f(X) – сложность вычисления аргументов при рекурсивном вызове процедуры

T_h(X) – сложность нерекурсивных вычислений

T_с(X, S) – сложность операции сравнения

T_s(S) – сложность вычисления нерекурсивного начального значения

T_c(S, S) – сложность операции сравнения для нерекурсивного начального значения

Пример:

Function F(n);

begin

If (n=0) or (n=1) {проверка возможности прямого вычисления}

       Then

             F:= 1

       Else

             F:=n*F(n-1); {рекурсивный вызов функции}

End;

X = x, 

S = 1, x = 1

f(X)=X-1,  FACTORIAL (x-1)

Tf(X)=1,    FACTORIAL (x-1)

Th(X) = 2,  FACTORIAL:= x * FACTORIAL (x-1)

Tc(X,S)=l,  x = 1

Ts(S) = 1.   FACTORIAL:= 1

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

Тa(x) = Тa(х-1)+4, Тa(1) = 2.

Ее решение – Тa(x) = 4х-2.

 

В случае косвенной рекурсии рекуррентное уравнение имеет вид:

 

                                                    

12) Оптимизация алгоритмов. Примеры.

Поиск алгоритма min сложности – оптимизация алгоритма.

 

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

 

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

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

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

 

Первый вид оптимизации имеет глобальный характер и (при удачной оптимизации) ведет к уменьшению порядка функции сложности - например, замена алгоритма с Т a (V) = O(F^S) на алгоритм с T a (V) = O(V⁴). Он зависит от того, как задача разбивается на подзадачи, насколько это разбиение свойственно самой задаче или является только искусственным приемом.

 

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

 

Пример: вычисления числа Фибоначчи через формулу:

 

 

13) Понятие сложности задачи и классы сложности задач. Понятия сводимости, полиномиальная сводимость.

Задачи:

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

сложность задачи – сложность самого простого алгоритма. Поиск алгоритма min сложности – оптимизация алгоритма.

Детерминированные вычисления – обычный, классический способ.

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

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

Классы сложности задач:

1. полиномиальные-их временная сложность ограничивается сверху некоторым полиномом.
2. экспоненциальные – в общем случае требуется кол-во операций, увеличивающееся с ростом n по крайней мере експоненциально.
3. NP – задачи, которые можно решить за полиномиальное время на недетерминированном вычислителе

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

вход для Q                Вход для Р               ответ Р                              Ответ Q

 

 

Полиномиальная сводимость – детерминированный полиномиальный алгоритм сводит одну задачу к другой

NPC – подкласс NP, любая задача NP сводится к ним

 

 

                        

14) Методы сортировок: сортировка массивов простыми включениями, сортировка массивов простым выбором, сортировка обменами. Анализ сложности алгоритмов сортировки.

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

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

 

Сортировка обменами:

Производится последовательное упорядочение смежных пар элементов массива: x [1] и x [2], x [2] и x [3], … x [ N -1] и x [ N ]. Если первый элемент больше второго, то элементы переставляются. В итоге, после N –1 сравнения максимальное значение переместится на место элемента X [ N ], т.е. "вверху" оказывается самый "легкий" элемент – отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента (X [ N –1]), таким образом второй по величине элемент поднимается на правильную позицию и т.д. Таким образом, нужно выполнить данную процедуру N –1 раз.

При первом прохождении нужно сравнить N –1 пар элементов, при втором – N –2 пары, при k -м прохождении – N ‑ k пар.

 

Program Sort1;

Const N=10;

Type mas=array[1..N] of real;

Var x:mas;

i,k:integer;

a:real;

Begin

For i:=1 to N do {Ввод элементов массива}

read(x[i]);

For i:=1 to N-1 do {Сортировка}

For j:=1 to N-i do

If x[j]>x[j+1] then Begin

   a:=x[j];

   x[j]:=x[j+1];

   x[j+1]:=a;

  End;

For i:=1 to N do {Вывод элементов массива}

Write(x[i],’ ‘)

End.

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