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


 

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

8747. Политическое развитие Западной Европы 37 KB
  Политическое развитие Западной Европы Особенности феодальной иерархии король - верховный сюзерен (господин) всех феодалов, первый среди равных в период раздробленности крупные светские и духовные феодалы - вассалы (военные слуги) к...
8748. Цивилизации в эпоху нового времени 42.5 KB
  Цивилизации в эпоху нового времени В новое время начала формироваться индустриальная цивилизация, которая строится на принципиально иных основах, чем предшествовавшая ей традиционная. ХVII и ХVIII столетия стали своего рода переходной эпохой, подгот...
8749. Цивилизация - это синоним культуры 36 KB
  Цивилизация - это синоним культуры. Цивилизация – это уровень, ступень общественного развития, материальной и духовной культуры это ступень развития, следующая за варварством. Существуют древние цивилизации и современные цивилизации, Западные и...
8750. Глобальные проблемы современности. Проблема предотвращения новой мировой войны 47.5 KB
  Глобальные проблемы современности 1. Проблема предотвращения новой мировой войны. Поиски путей предотвращения мировых конфликтов начались практически сразу после окончания второй мировой и победы над нацизмом. Тогда было принято решение и о со...
8751. Экономическая сфера общества. Структура отношений собственности в современной экономике 47.5 KB
  Экономическая сфера общества. Структура отношений собственности в современной экономике Экономика играет огромную роль в жизни общества. Экономика - в широком смысле обычно понимают систему общественного, производства, т. е. процесс создания ма...
8752. Рыночные отношения в современной экономике 31 KB
  Вариант 1. Рыночные отношения в современной экономике Существуют два варианта организации экономической жизни общества: командная экономика и рыночная экономика. Основными признаками командной экономики являются: производство товаров в соответ...
8753. Государство и экономика 62 KB
  Государство и экономика. Современный рынок не регулируется только с помощью механизма свободного ценообразования. Действуя стихийно, законы рынка не только дают положительный эффект, но и порождают негативные тенденции в экономике, такие, как монопо...
8754. Нации и межнациональные отношения 43.5 KB
  Нации и межнациональные отношения Этносы - большие группы людей, выделяемые на основе общности культуры, языка, сознания нерасторжимости исторической судьбы. Социальные общности, выделяемые по этническому признаку, многообразны. Прежде всего, э...
8755. Государство. Три ветви власти 39.5 KB
  Государство. Три ветви власти Государство - важнейший институт политической системы общества. В политической науке до сих пор не достигнут консенсус по вопросу об определении понятия государства. Различные теории выдвигают на первый план один из асп...