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.  У якому випадку зручно використовувати оператор циклу з параметром?


 

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

79626. К ПРОБЛЕМЕ ПЕРИОДИЗАЦИИ ПСИХИЧЕСКОГО РАЗВИТИЯ В ДЕТСКОМ ВОЗРАСТЕ 167 KB
  Проблема периодизации психического развития в детском возрасте является фундаментальной проблемой детской психологии. Ее разработка имеет важное теоретическое значение поскольку через определение периодов психического развития и через выявление закономерностей переходов от одного периода...
79627. РАЗВИТИЕ ГОСУДАРСТВЕННО-ПРАВОВЫХ РЕФОРМ В СТРАНАХ, ОБРАЗОВАВШИХСЯ НА ОСНОВЕ РАСПАДА СОЮЗА СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК: КЛАССИФИКАЦИОННЫЙ ПОДХОД 82 KB
  Одним из его наиболее значимых признаков является верховенство Конституции и законов на всей территории государства. Так например можно обозначить время принятия конституции после образования государства динамику становления национальной системы права направленность конституционных реформ...
79628. ОБЩАЯ ХАРАКТЕРИСТИКА НЕКОТОРЫХ ОСОБЕННОСТЕЙ ГОСУДАРСТВЕННО-ПРАВОВОГО СТРОИТЕЛЬСТВА В КОРЕЙСКОЙ НАРОДНОЙ ДЕМОКРАТИЧЕСКОЙ РЕСПУБЛИКЕ 145.5 KB
  На волне возросшего интереса к Корее появилось вместе с тем немало весьма поверхностных работ, в которых содержаться конъюнктурные оценки, и прослеживается позиция западных исследователей. В них обосновывалась неизбежность свертывания политических, экономических и военных отношений России...
79629. ГОСУДАРСТВО И МЕСТНОЕ САМОУПРАВЛЕНИЕ В ЗАРУБЕЖНЫХ СТРАНАХ: ОТДЕЛЬНЫЕ АСПЕКТЫ ИЗ ВЗАИМООТНОШЕНИЙ 84 KB
  Тем самым, идея местного самоуправления в зарубежных государствах, зародившись и развиваясь теоретически, практически смогла воплотиться лишь в период буржуазных революций. Возможным объяснением этого может явиться то, что « само становление же местного самоуправления было связано с процессами перехода...
79630. ПЕРСПЕКТИВЫ РАЗВИТИЯ ИСПОЛНИТЕЛЬНОГО ПРОИЗВОДСТВА В РОССИЙСКОЙ ФЕДЕРАЦИИ 108.5 KB
  Принятие Федеральных законов О судебных приставах и Об исполнительном производстве предполагает необходимость существенного обновления нормативно-правовой базы исполнительного производства. Из статьи следует что законодательство Российской Федерации об исполнительном производстве состоит...
79631. ОБУСЛОВЛЕННОСТЬ И ОПЫТ УГОЛОВНО-ПРАВОВОЙ БОРЬБЫ С УКЛОНЕНИЯМИ ОТ ОТБЫВАНИЯ ЛИШЕНИЯ СВОБОДЫ В ЗАРУБЕЖНОМ ЗАКОНОДАТЕЛЬСТВЕ 131.5 KB
  В зависимости от типичных правовых систем мира сначала будет предпринята попытка рассмотреть наиболее показательный зарубежный опыт кратковременного пребывания осужденного к лишению свободы за пределами исправительного учреждения и отсрочки отбывания наказания либо исполнения приговора суда...
79632. ЗАКОННОСТЬ И ОБОСНОВАННОСТЬ СУДЕБНОГО ПРИГОВОРА 110.5 KB
  Цель уголовного процесса: установление истины по уголовному делу изобличение и наказание лица совершившего преступление и защита невиновного человека от необоснованного обвинения и осуждения достигается при постановлении судом правосудного приговора.
79633. ДОТАЛЬНЫЕ СОГЛАШЕНИЯ И DONATIO PROPTER NUPTIAS В РИМСКОМ ПРАВЕ 76 KB
  Поимущественные отношения супругов в римском праве определялись не браком, а переходом женщины во власть мужа, эффект которого подобен усыновлению. Брак сам по себе никак не сказывается на имущественных правах сторон: женщина по прежнему остается под опекой и не терпит никаких дополнительных...
79634. ЗАКОННЫЙ РЕЖИМ ИМУЩЕСТВА СУПРУГОВ 73.5 KB
  Имущество имеющееся у супругов состоит из имущества собственником которого является каждый из супругов личное имущество и имущества приобретенного во время брака совместное имущество супругов. Определяющим признаком правового режима является бездолевой характер поскольку доли супругов в их общем...