69892

Дослідження ефективності алгоритму

Лабораторная работа

Информатика, кибернетика и программирование

Мета: набуття навичок визначення часової складності алгоритму. Теоретичні питання план Функція складності алгоритму. Види функції складності алгоритмів. Часова функція складності.

Украинкский

2014-10-12

3.19 MB

2 чел.

Лабораторна робота №2

Тема. Дослідження ефективності алгоритму

Мета: набуття навичок визначення часової складності алгоритму.

Професійна спрямованість: дана лабораторна робота є складовою частиною професійної підготовки фахівця з інформатики до роботи.

Теоретичні питання (план)

  1.  Функція складності алгоритму.
  2.  Види функції складності алгоритмів.
  3.  Часова функція складності.
  4.  Аналіз функції складності за програмою.

Хід виконання роботи

  1.  Ознайомтеся з основними теоретичними відомостями.
  2.  Згідно номеру свого варіанту оберіть умову задачі.
  3.  Побудувати блок-схему.
  4.  Провести аналіз складності алгоритму та побудувати графік ефективності програми.

Теоретичні відомості

Для оцінки якості алгоритму вводиться поняття складності алгоритму, або обернене поняття – ефективність алгоритму. Чим більший час та об’єм пам’яті необхідно для реалізації алгоритму, тим більша його складність та відповідно нижча ефективність. Складність алгоритму поділяється на часову та ємнісну. Часова складність – це критерій, що характеризує часові витрати на реалізацію алгоритму. Ємнісна складність – критерій, що характеризує витрати пам’яті з тією ж метою. Залежно від конкретної форми цих критеріїв складність алгоритму поділяється на практичну та теоретичну. Практична часова складність зазвичай оцінюється у часових одиницях (секунди, мілісекунди, кількість часових тактів процесора, кількість виконання циклів і т.п.). Практична ємнісна складність виражається у бітах, байтах, словах і т.п.

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

Часто говорять, що час виконання алгоритму має порядок T(N) від вхідних даних розміру N. Одиниця вимірювання T(N) точно не визначена, але в більшості випадків розуміють під нею кількість інструкцій, які виконуються на ідеалізованому комп’ютері.

Для багатьох програм час виконання дійсно є функцією вхідних даних, а не їх розміру. У цьому випадку визначають T(N) як час виконання в найгіршому випадку, тобто, як максимум часів виконання за всіма вхідними даними розміру N. Поряд з тим розглядають Tср(N) як середній (в статистичному розумінні) час виконання за всіма вхідними даними розміру N. Хоча Tср(N) є достатньо об’єктивною мірою виконання, але часто неможливо передбачити, або обґрунтувати, рівнозначність усіх вхідних даних. На практиці середній час виконання знайти складніше, ніж найгірший час виконання, так як математично це зробити важко і, крім цього, часто не буває простого визначення поняття „середніх” вхідних даних. Тому, в основному, користуються найгіршим часом виконання як міра часової складності алгоритмів.

Аналіз часу виконання алгоритмів

Час виконання алгоритму можна оцінювати шляхом підрахунку кількості «базових операцій», що виконуються, - як функцію від розміру вхідних даних.

Приймаються наступні припущення про гіпотетичну обчислювальну машину (виконавця):

  •  для виконання «простої» операції (+, -, *, /, =, if, call)  потрібно один часовий крок (такт обчислювальної машини);
  •  звертання до пам’яті (читання, запис) виконуються за один часовий крок;
  •  цикли та підпрограми складаються із послідовності простих операцій.

Приклад 1. Обчислимо кількість T(N) операцій, що виконуються алгоритмом пошуку максимального елемента в масиві:

  •  
  •  

Кількість T(N) операцій, що виконує алгоритм у найгіршому випадку:

T(N) = 1+(2+2)N+1 = 2+4N.

Найкращий спосіб порівняння ефективності алгоритмів полягає у співставленні їх порядків складності. Цей метод застосовується як для часової, так і ємнісної складності. Порядок складності виражає його ефективність через кількість даних, що обробляються.

Порядок алгоритму – це функція, що домінує над точним виразом часової складності. Функція f(n) має порядок O(g(n)), якщо константа k і лічильник n0 такі, що f(n)≤kg(n) для n>n0. Дійсний час є функція, що залежить від довжини масиву.

Наприклад, відомо, що точний час обробки масиву визначається з рівняння

Дійсний час (довжина масиву) = Довжина масиву2 + 5*Довжина масиву + 100.

Грубе значення визначається допоміжною функцією:

Оцінка часу (довжина масиву) = 1,1*Довжина масиву2.

Функція складності О виражає відносну швидкість алгоритму в залежності від деякої змінної (або змінних).

Існує три важливих правила для визначення функції складності:

  1.  O(kf) = O(f).
  2.  O(fg) = O(f)O(g) або O(f/g) = O(f)/O(g).
  3.  O(f+g) дорівнює домінанті  O(f) і O(g).

Тут k позначає константу, а f і g – функції.

Перше правило декларує, що постійні множники не мають значення для визначення порядку складності, наприклад:

O(1,5N) = O(N).

З другого правила слідує, що порядок складності добутку двох функцій дорівнює добутку їх складностей, наприклад:

O(17N*N) = O(17N)O(N) = O(N)O(N) = O(N*N) = O(N2).

З третього правила слідує, що порядок складності функцій визначається як порядок домінанти першого і другого доданків, тобто вибирається найбільший порядок, наприклад:

O(N5 + N2) = O(N5).

Види функції складності алгоритмів

Функція складності О(1). В алгоритмах константної складності більшість операцій в програмі виконуються один або декілька раз. Будь-який алгоритм, що завжди потребує незалежно від розміру даних одного і того ж часу, має константну складність.

Функція складності O(N). Час роботи програми лінійний, коли кожний елемент вхідних даних треба опрацювати лише лінійне число раз.

Функція складності O(N2), O(N3), O(Na) – поліноміальна функція складності.

Функція складності O(log2N), O(N log2N). Такий час роботи мають ті алгоритми, які поділяють велику проблему на множину невеликих, а потів, вирішивши її, об’єднують рішення.

Функція складності O(2N). Експоненціальна складність. Такі алгоритми найчастіше виникають у результаті підходу, що називається «метод грубої сили».

Часова функція складності

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

Алгоритми без циклів та рекурсивних викликів мають константну складність. Якщо немає рекурсії та циклів, то всі керівні структури можуть бути зведені до структур константної складності. Отже, весь алгоритм також характеризується константною складністю. Визначення складності алгоритму переважно зводиться до аналізу циклів та рекурсивних викликів.

Наприклад, розглянемо алгоритм обробки елементів масиву:

For i:=1 to N do

Begin

End;

Складність цього алгоритму O(N), так як тіло циклу виконується N раз, і складність тіла циклу дорівнює О(1). Якщо один цикл вкладений в інший та обидва цикли залежать від розміру однієї і тієї ж змінної, то вся конструкція характеризується квадратичною складністю:

For i:=1 to N do

For j:=1 to N do

Begin

 

End;

Складність цієї програми O(N2).

Аналіз функції складності за програмою

Існує два способи аналізу складності алгоритму: висхідний (від внутрішніх керівних структур до зовнішніх) та низхідний (від зовнішніх структур до внутрішніх).

Приклад 2. Оцінимо складність програми «Трійки Піфагора»:

O(A) = O(1) + O(1) + O(1) = O(1);

O(B) = O(C) = O(J) = O(K) = O(L) = 1;

O(H) = O(1) + O(1) + O(1) = O(1);

O(F) = O(1) + O(H) = O(1) + O(1) = O(1);

O(I) = O(N)* (O(F)+O(J)) = O(N) * O(домінанти умови) = O(N);

O(G) = O(N)* (O(C) + O(I) + O(K)) = O(N)*(O(1) + O(N) + O(1)) = O(N2);

O(E) = O(N)*(O(B) + O(G) + O(L)) = O(N)*O(N2) = O(N3);

O(D) = O(A)+ O€ = O(1) + O(N3) = O(N3).

Складність даного алгоритму O(N3).

Варіанти завдань

Завдання 1.

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

Варіант 1

program matrixadd(input, output);

const maxN=l0;

var p, q, r: array [0..maxN, 0..maxN] of real;

N, i, j: integer;

begin

readln (N) ;

for i:=0 to N-l do for j:=0 to N-l do read(p[i, j]);

for i:=0 to N-l do for j:=0 to N-l do read(q[i, j]);

for i:=0 to N-l do for j:=0 to N-l do r[i, j]:=p[i, j]+q[i, j];

for i:=0 to N-l do for j:=0 to N do

if j=N then writeln else write(r[i, j]);

end.

Варіант 2

program gauss(input, output);

const maxN=50;

var a: array[1..maxN, l..maxN] of real;

i, J, k, N: integer;

begin

readln (N) ;

for j:=l to N do

begin for k:=l to N+1 do read(ab, k]); readln end;

for i:=l to N do

for j:=i+l to N do

for k:=N+l downto i do

[ab,k]:=aIj,k]-a[i,k]*ab,i]/a[i,i];

for j:=l to N do

begin for k:=l to N+1 do write(ab, k]); writeln end;

end.

Варіант 3

procedure eliminate;

var i, j, k, max: integer;

t: real;

begin

for i:=l to Ndo

begin

max:=i;

for j:=i+l to N do

if abs(a[j, i])>abs(a[max, i]) then max:=j;

for k:=i to N+l do

begin t:=a[i, k]; a[i, k] :=a[max, k]; a[max, k] :=t end;

for j:=i+l to N do

for k:=N+l downto i do

ab,k]:=ab,k]-a[i,k]*ab,i]/a[i,i];

end

end;

Варіант 4

Варіант 5

Варіант 6

var s:string;

    r:real;

    i,j,n:integer;

begin

    r:=0;

    readln(s);

    for i:=1 to length(s) do begin

       n:=0;

       for j:=1 to length(s) do begin

          if s[i]=s[j] then inc(n);

       end;

       r:=r+1/n;

    end;

    writeln('количество различных букв = ', r:1:0);

end.

Варіант 7

program MaximuM;

const

    m = 7;

    n = 4;

var

Matrix: array[1..m, 1..n] of integer;

i,j,max,smax: integer;  

Begin

Writeln('Матрица:');

max:= -41;

smax:= 1;

Randomize;

for i:=1 to m do begin

 for j:=1 to n do begin

                 Matrix[i, j]:=Random(71)-40;

                 Write( (Matrix[i, j]):4 );

                 if (Matrix[i, j] > max) then

                     begin

                     max:= Matrix[i, j];

                     smax:= i;   

                     end;

                 end;

                Writeln;

                end;

Writeln('Максимальный элемент ', max,' в строке ',smax,':');

Writeln('Новая матрица:');

for i:= m downto smax+1 do begin

for j:=1 to n do begin

     if (i = smax + 1) then Matrix[i, j]:= Matrix[1, j] else

     if smax <> m then Matrix[i, j]:= Matrix[i-1, j];

                 end;

                end;

for i:=1 to m do begin 

 for j:=1 to n do begin

     Write( (Matrix[i, j]):4 );

                 end;

     Writeln;

                end;

Readln;

End.

Варіант 8

Варіант 9

Варіант 10

Варіант 11

Варіант 12

Варіант 13

program minImax;

uses crt;

const

    N = 9;

type Mas = array[1..N,1..N] of integer;

var

  M: Mas;

  i,j,s: integer;

  min,max,jmin,imax: integer;

Begin

clrscr;

Writeln;

Randomize;

TextAttr:=15;

for i:=1 to N do begin         

 for j:=1 to N do begin

M[i,j]:=Random(10);

Write(' ',M[i,j]:3);

                 end;

Writeln;

                end;

max:=M[1,1];imax:=1;

min:=M[1,1];jmin:=1;

for i:=1 to N do begin         

for j:=1 to N do begin

 if M[i,j] > max then begin

                    max:=M[i,j];imax:=i;

                    end;

 if M[i,j] < min then begin

                    min:=M[i,j];jmin:=j;

                    end;

 end;

end;

Writeln;

Writeln('max= ',max,' в строке ',imax);

Writeln('min= ',min,' в столбце ',jmin);

Writeln;

for i:=1 to N do begin           

for j:=1 to N do begin

 if (i=imax) or (j=jmin) then TextAttr:=11 else TextAttr:=8;

 Write(' ',M[i,j]:3);

                 end;

Writeln;

                end;

Writeln;

Write('Скалярное произведение ',imax,' строки на ',jmin,' столбец: ');

for i:= 1 to N do

s:= s + M[i,jmin]*M[imax,i];         

Write(s);

Readln;

End.

Варіант 14

program M_x_N;

type

Tmatrix = array[1..1] of integer;

var

Matrix: ^Tmatrix;

Sums: ^Tmatrix;

Nums: ^Tmatrix;

 i,j,k1,k2,m,n: integer;

Begin

Write('Введите n:');

Readln(n);

Write('Введите m:');

Readln(m);

Write('Введите k1:');

Readln(k1);

Write('Введите k2:');

Readln(k2);

GetMem(Matrix,n * m * sizeOf(integer));

GetMem(Sums,n * sizeOf(integer));

GetMem(Nums,n * sizeOf(integer));

for j:=1 to n do begin

Nums^[j]:= 0;  

Sums^[j]:= 0;  

                end;

Writeln;

Writeln('Матрица:');

Randomize;

for i:=1 to m do begin  

for j:=1 to n do begin

                 Matrix^[(j-1)*n+i]:=Random(71)-40;  

         

                 Write( (Matrix^[(j-1)*n+i]):4 );

                 if (Matrix^[(j-1)*n+i] mod k1 = 0) or (Matrix^[(j-1)*n+i] mod k2 = 0) then

                     begin

                     Sums^[j]:= Sums^[j] + Matrix^[(j-1)*n+i];

                     Nums^[j]:= Nums^[j] + 1;  

                     end;

                 end;

                Writeln;

                end;

Writeln('Число элементов кратных ', k1,' и ',k2,':');

for j:=1 to n do

Write( (Nums^[j]):4 );

Writeln;

Writeln('Сумма по столбцам:');

for j:=1 to n do

Write( (Sums^[j]):4 );

FreeMem(Sums,n * sizeOf(integer));  

FreeMem(Nums,n * sizeOf(integer));

FreeMem(Matrix,n * m * sizeOf(integer));

Readln;

End.

Рекомендована література

Базова

  1.  Ахо А.В. Структуры данных и алгоритмы / Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д./ М: Вильямс, 2003.— 384 с.
  2.  Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989. — 360 с.

Зміст звіту

Тема роботи; умова задачі; обчислення числа базових операцій та функції складності; графік ефективності програми; висновки за результатами розв’язання.

Контрольні запитання

  1.  Дайте визначення функції складності.
  2.  Вкажіть види функцій складності алгоритмів.
  3.  Що включає поняття складності алгоритму?
  4.  Вкажіть правила для визначення функції складності.
  5.  Які види функції складності існують?
  6.  Яким чином визначається часова функція складності?
  7.  Назвіть способи аналізу функції складності за програмою.
  8.  Як працює оператор циклу з параметром?
  9.  У якому випадку зручно використовувати оператор циклу з параметром?


 

А также другие работы, которые могут Вас заинтересовать

18059. Практикум по арбитражному процессу 1.2 MB
  Практикум по арбитражному процессу Учебное пособие для студентов юридических вузов и факультетов Под редакцией доктора юридических наук профессора В. В. Яркова и кандидата юридических наук доцента С.Л. Дегтярева 2е издание переработанное и дополненное .: ...
18060. ИСТОРИЯ ДЕНЕЖНО-КРЕДИТНОЙ СИСТЕМЫ РОССИИ 1.53 MB
  История денежнокредитной системы России В пособии раскрывается процесс зарождения и формирования денежной системы возникновение банковского дела становления и развития банковской системы России. В первой части излагается процесс формирования и развития денежной с...
18061. Філософія права. Підручник 966 KB
  Підручник присвячено філософії права. У ньому висвітлюються зміст призначення та історичний розвиток філософії права а також її основні проблеми: правова онтологія правова антропологія правова аксіологія тощо. Значну увагу у виданні приділено аналізу сучасних філо...
18064. ИССЛЕДОВАНИЕ РАСПРЕДЕЛЕНИЯ ДАВЛЕНИЯ ПО ПОВЕРХНОСТИ ОБТЕКАЕМОГО ТЕЛА В ПОТОКЕ ДОЗВУКОВОЙ СКОРОСТИ 4.67 MB
  Лабораторная работа №6 по предмету Экспериментальная аэродинамика ИССЛЕДОВАНИЕ РАСПРЕДЕЛЕНИЯ ДАВЛЕНИЯ ПО ПОВЕРХНОСТИ ОБТЕКАЕМОГО ТЕЛА В ПОТОКЕ ДОЗВУКОВОЙ СКОРОСТИ Цель работы получение результатов распределения давления построенных для крыла в координат...
18065. Знайомство з документацією супроводження програмних продуктів 320 KB
  Тема: Знайомство з документацією супроводження програмних продуктів. Понятие жизненного цикла ПО В первой лекции говорилось о том что сложную программную систему построить простыми методами невозможно. Ее разработка с неизбежностью будет тоже сложной деятельнос...
18066. Исследование элементов электрической цепи при постоянном токе 22.7 KB
  Исследование элементов электрической цепи при постоянном токе. Цель работы: приобрести практические навыки экспериментального определения параметров элементов. Содержание отчета. 2.1 Измерение сопротивлений активных элементов Схема электрической цепи ...
18067. Исследование элементов цепи при переменном токе 27.27 KB
  Цель работы: Исследование элементов цепи при переменном токе Содержание отчета. 2.1 Измерение активного сопротивления Схема электрической цепи: Частота и величина напряжения источника питания значение сопротивления в соответствии с номером рабочего места: ...