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


 

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

34458. Искусство Западной Европы ХVII века. Специфика голландской живописи. Творчество Ф. Хальса, В.Дельфтского, Рембрандта 19.83 KB
  Отсюда широкий диапазон живописи этого столетия узкая специализация по отдельным видам тематики: портрет и пейзаж натюрморт и анималистический жанр. прекрасно демонстрирует эволюция творчества одного из крупнейших портретистов Голландии Франса Халса около 1580 1666. В 10 30х годах Халс много работает в жанре группового портрета. Индивидуальные портреты Халса исследователи иногда называют жанровым в силу особой специфичности изображения.
34459. Искусство Западной Европы ХVII века. Своеобразие испанской культуры ХVII в. Творчество Д.С. Веласкеса 18.46 KB
  Веласкеса Со второй половины XV в. Самый замечательный художник золотого испанского века Диего Родригес де Сильва Веласкес 1599 1660. Веласкес севильянец учился у Пачеко. Интересно что у Веласкеса типичнейшего испанца почти отсутствуют произведения на религиозные сюжеты а те которые он избирает трактуются им близко к бодегонес как жанровые сцены Христос в гостях у Марии и Марфы.
34460. Искусство Западной Европы ХVII века. Своеобразие исторического пути Франции ХVII в. Н. Пуссен – основоположник классицизма в живописи 19.64 KB
  Творчество замечательного рисовальщика и гравера Жака Калло 1593 1635 завершавшего свое образование в Италии явно испытало заметное влияние итальянского искусства. На творчестве Луи Ленена 1593 1648 отчетливо прослеживается влияние голландского искусства художник изображает крестьян без пасторальности без сельской экзотики не впадая в слащавость и умиление. Основой теории классицизма был рационализм опирающийся на философскую систему Декарта предметом искусства классицизма провозглашалось только прекрасное и возвышенное этическим и...
34461. Развитие бытового жанра в Англии ХVIII в. У. Хогарт. Влияние идей просветителей на портрет и пейзаж середины и второй половины ХVIII в. Английская школа портрета Дж. Рейнольдс. Т. Гейнсборо 18.89 KB
  Гейнсборо. Томас Гейнсборо 1727 1788 второй великий портретист XVIII столетия. В английской живописи эпохи Просвещения Рейнолдс и Гейнсборо выражают как бы две стороны просветительской эстетики: рационалистическую и эмоциональную. Для формирования Гейнсборо проведшего свою юность и молодость в провинции и сохранившего глубокую любовь к природе своего края старые мастера за исключением разве ван Дейка не имели такого значения как для Рейнолдса.
34462. Развитие искусства Италии в ХVIII в. Италия. Творчество Д.Б.Тьеполо. Развитие пейзажа (А. Каналетто, Т. Гварди) 17.04 KB
  был Джованни Баттиста Тьеполо 1696 1770 последний представитель барокко в европейском искусстве. Тьеполо автор гигантских росписей как церковных так и светских в которых архитектура природа люди звери сливаются в одно декоративное целое в единый декоративный поток. У Тьеполо был огромный декоративный дар и высокая колористическая культура как правило вообще присущая венецианским художникам. В одном из полотен для палаццо Дольфино в Венеции Триумф Сципиона особенно наглядно видно как умел и любил Тьеполо писать триумфальные...
34463. Творчество Ж.Л. Давида. Ж.Д. Энгр и формирование принципов неоклассицизма 18.99 KB
  В преддверии Великой французской революции в живописи Франции появляется Жак Луи Давид 1748 1825. Познакомившись с памятниками античности испытав влияние трудов Винкельмана и живописи немецкого классицистического художника Рафаэля Менгса Давид находит свой путь. Так выкристаллизовывался новый стиль и Давид в своей картине Клятва Горациев 1784 1785 выступил его глашатаем.
34464. Эстетическая программа романтизма. Романтизм во Франции. Творчество Т. Жерико и Э. Делакруа. Романтизм в Германии. Творчество Ф.О. Рунге и К.Д. Фридриха 19.64 KB
  Делакруа. Энгр непримиримый враг романтиков до конца жизни говорил что Делакруа пишет бешеной метлой а Делакруа обвинял Энгра и всех художников Школы в холодности рассудочности в отсутствии движения в том что они не пишут а раскрашивают свои картины. Об этом говорят и темы экзотического Востока и иллюстрации к Байрону и Шелли и Охота на львов и портрет 20летнего Делакруа. Истинным вождем романтизма стал Эжен Делакруа 1798 1863 сын бывшего члена революционного Конвента Его первые работы Ладья Данте и...
34465. Реализм в искусстве Франции второй половины ХIХ века. Пейзаж барбизонской школы. Крестьянский жанр Ф. Милле 17.83 KB
  Одно время работал в Барбизоне Жан Франсуа Милле 1814 1875. Родившийся в крестьянской среде Милле навсегда сохранил связь с землей. Крестьянский мир основной жанр Милле.
34466. Искусство импрессионизма. История возникновения группировки импрессионистов и эстетическая платформа. Живописная система импрессионистов. Основные представители течения 14.24 KB
  Искусство импрессионизма. Импрессионизм франц. предопределил направленность импрессионизма и который также и в 1870 80е гг. Название импрессионизм возникло после выставки 1874 на которой экспонировалась картина К.