69892

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

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

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

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

Украинкский

2014-10-12

3.19 MB

3 чел.

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


 

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

22957. Особливості сучасної західної філософії. Вітчизняні філософські традиції 54 KB
  Антропологізм ця тенденція орієнтує філософію на дослідження людини і світу культури. Сутність тенденції виражають наступні ідеї: вивчення життя окремої людини стоїть вище є більш значним ніж вивчення великих людських спільнот класів народів націй. відмова від розуміння сучасної людини як свободної і розумної здатної переробляти світ. Відмова від такого розуміння і перехід до розуміння людини яка жорстко обумовлена економікою політикою релігією та ін.
22958. Проблема свідомості 62.5 KB
  Свідомість самосвідомість мова. Проблема свідомості одна з найбільш важливих для дослідження і одна з найбільш загадкових оскільки свідомість не існує як окремий предмет дослідження. Свідомість присутня в кожному образі думці поєднує наші почуття і думки. Свідомість завжди проявляється через якийсь конкретний зміст який виражається думками знаннями образами.
22959. Психіка людини 56 KB
  Голодна людина має енергію скеровану на пошук їжі. Людина народжується в суспільстві яке задає певні правила виховання. Людина деякі з цих правил бере добровільно в свою свідомість як ті правил яким вона буде підкорятись. Людина перестає контролювати себе і відчуває певне задоволення.
22960. ПИТАННЯ ПРО ПРИРОДУ ЛЮДИНИ 68 KB
  Питання сутності людини це питання про те які глибинні людські якості визначають специфіку людини і проявляється зовні в її природі. Природи людини дуже суперечлива. Наші біологічні властивості це лише передумови виникнення людини а якщо не буде соціальних умов то людина не виникне.
22961. Виявлення сутності суспільства 63 KB
  Пізнання. Уявлення про знання і пізнання. Теорія пізнання її предмет і метод. Чуттєве і раціональне пізнання.
22962. Форми раціонального пізнання 62 KB
  На їх основі створюються більш складні форми наукового пізнання: 1. Умовивід це форма мислення за допомогою якої з раніше встановленого знання або судження виводяться нові знанні нові судження. Напрямком сучасної західної філософії для якої головна проблема це звязок пізнання і розуміння герменевтика.
22963. Наукове пізнання 46.5 KB
  Це сукупність способів принципів пізнання прийомів і процедур якими керуються в тій або іншій галузі науки. Ця дисципліна входить до якоїсь галузі науки. Для сучасної науки в цілому характерним є методологічний плюралізм тобто вона прагне використовувати будьякі принципи і прийоми дослідження в їхньому сполученні і взаємодії. Питання етики науки.
22964. Філософський зміст буття 40.5 KB
  Форми буття. Це питання стосовно буття. Буття як філософська категорія означає умоосягаєму одвічну першореальність яка обумовлює все існуюче и пронизує його.
22965. Поняття про світогляд 53 KB
  Особливості ставлення людини до світу 2. А ми пристосовуємось до світу іншим способом ми активно перетворюємо його прагення пристосувати світ до себе змінюючи його своєю діяльністю олюднення світу тобто робити світ більш придатним до людини. Все це означає пізнання людини пізнання світу пізнання одночасно. Висновок: людині щоб існувати треба перетворювати дійність але для цього це перетворювання відбувається в голові людини.