Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Асимптотичні характеристики складності алгоритму. Алгоритми з поліноміальною та експоненціальною складністю
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
КН
Кафедра:
Кафедра ЕПМС
Інформація про роботу
Рік:
2014
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Варіант:
7
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 2
з дисципліни:
«Алгоритми та методи обчислень»
на тему:
“Асимптотичні характеристики складності алгоритму.
Алгоритми з поліноміальною та експоненціальною складністю”
Мета роботи: ознайомитись з асимптотичними характеристиками складності та класами складності алгоритмів.
Теоретична частина
В процесі розв’язку задачі вибір алгоритму викликає певні труднощі. Алгоритм повинен задовільняти вимогам, які часом суперечать одна одній:
= бути простим для розуміння, переводу в програмний код, відлягодження.
= ефективно використовцвати комп'ютерні ресурси і виконуватись швидко.
Якщо програма повинна виконуватись декілька разів, то перша вимога більш важлива. Вартість робочого часу програміста перевищує вартість машинного часу виконання програми, тому вартість програми оптимізується по вартості написання ( а не виконання) програми. Якщо задача вимагає значних обчислювальних витрат, то вартість виконання програми може перевищити вартість написання програми, особливо коли програма повинна виконуватись багаторазово. Але навіть в цій ситуації доцільно спочатку реалізувати простий алгоритм, і з'ясувати яким чином повинна себе поводити більш складна програма.
На час виконання програми впливають наступні чинники:
= ввід інформації в програму
= якість скомпільованого коду
= машинні інструкції, які використовуються для виконання програми
= часова складність алгоритму (ЧС)
Часова складність є функцією від вхідних даних. Для деяких задач ЧС залежить від самих вхідних даних (знаходження найбільшого спільного дільника двох чисел), для інших – від їх "розміру" (задачі сортування).
Коли ЧС є функцією від самих даних, її визначають як ЧС для найгіршого випадку, тобто як найбільшу кількість інструкцій програми серед всіх можливих вхідних даних для цього алгоритму.
Використовується також ЧС в середньому ( в статистичному сенсі ), як середня кількість інструкцій по всім можливим вхідним даним. На практиці ЧС в середньому важче визначити ніж ЧС для найгіршого випадку, черезте що це математично важка для розв'язання задача, та, крім того, іноді важко визначити, що означає "середні" вхідні дані.
Коли ЧС є функцією від кількості вхідних даних, аналізується швидкість зростання цієї функції.
Асимптотичні співвідношення
Для опису швидкості зростання функцій використовується О-символіка. Функція f(n) має порядок зростання O(g(n)), якщо що існують додатні константи С i n0 такі, що
f(n) <= С*g(n), для n > n0.
Позначемо функцію яка виражає залежність часової складності від кількості вхідних даних (n) через L(n) Тоді, наприклад, коли говорять, що часова складність L(n) алгоритму має порядок(степінь) зростання O(n2) (читається як "О велике від n в квадраті, або просто "о від n в квадраті", то вважається, що існують додатні константи c i n0 такі, що для всіх n, більших або рівних n0, виконується нерівність L(n)<=cn2.
Наприклад, функція L(n) = 3n3+2n2 має порядок зростання O(n3).
Нехай n0=0 і с = 5. Очевидно, що для всіх цілих n>=0 виконується нерівність 3n3+2n2 <= 5n3.
Коли кажуть, що L(n) має степінь зростання O(f(n)) , то вважається, що f(n) є верхньою границею швидкості зростання L(n). Щоби вказати нижню границю швидкості зростання L(n) використовують позначення ((g(n)) , що означає існування такої константи с , що для нескінченогї кількості значень n виконується нерівність L(n)>=c g(n).
На практиці визначення порядку зростання є задачею, що цілком вирішується за допомогою кількох базових принципів. Існують три правила для визначення складності:
O(с* f(n))=O(f(n))
O(f(n) + g(n)) = O(max(f(n), g(n)))
O(f(n) * g(n)) = O(f(n)) * O(g(n))
Перше правило декларує, що постійні множники не мають значення для визначення порядку зростання.
Друге правило називається "Правило сум".
Це правило використовується для послідовних програмних фрагментів з циклами та розгалуженнями.
Порядок зростання скінченої послідовності програмних фрагментів (без врахування констант) дорівнює порядку зростання фрагменту з найбільшою часовою складністю.
Якщо алгоритм складається з двох фрагментів, функції часових складностей яких L1(n) і L2(n) мають ступені зростання O(f(n)) і O(g(n)) відповідно, то алгоритм має степінь зростання O(max(f(n),g(n))).
Третє правило називається "Правило добутків".
Правило добутків полягає в наступному. Якщо L1(n) і L2(n) мають ступені зростання O(f(n)) і O(g(n))
відповідно, то добуток L1(n) L2(n) має степінь зростання O(f(n)g(n)) .Прикладом може бути фрагмент програми "цикл в циклі".
Послідовність виконання роботи
Завдання
5
__________________________________________________________________________________________
Функція має найбільшу степінь зростання, а саме en
Побудуємо графіки, для k = 3,4,5; n = (1,2,…,10)
Для спрощення виберемо відповідно до к наступні поліноми , та
Побудуємо графіки :
; n = 1,2,…
Текст програми
#include<iostream>
#include <Windows.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
BOOL Line(HDC hdc, int x1, int y1, int x2, int y2){
MoveToEx(hdc, x1, y1, NULL);
return LineTo(hdc, x2, y2);
}
int main(void)
{
int k,y=151,x0=420;
float x;
cin>>k;
HDC hDC = GetDC(GetConsoleWindow());
HPEN Pen = CreatePen( PS_SOLID,1, RGB(255, 255, 255));
SelectObject( hDC, Pen );
MoveToEx( hDC, 220, 151, NULL );
LineTo( hDC, 620, 151);
MoveToEx( hDC, 420, 0, NULL );
LineTo( hDC, 420,300);
for(int i = 250; i < 700; i+=25){
Line(hDC,i+19,y-2,i+19,y+2);
}
for(int i = 0; i < y*2; i+=25){
Line(hDC,x0-2,i+24,x0+2,i+24);
}
COLORREF color = RGB(100,150,255);
HPEN pen = CreatePen(PS_SOLID,3,color);
SelectObject(hDC,pen);
for (x = -9.0f; x <= 9.0f; x += 0.01f ) // O(100,85) - center
{
MoveToEx( hDC,20*(x+15)+120, -15*((exp(x))/(pow(x,k)))+150, NULL );//10 - scale
LineTo( hDC, 20*(x+15)+120, -15*((exp(x))/(pow(x,k)))+150);
}
system("pause");
return 0;
}
Результати виконання програми
K=3
/
K=4
/
K=5
/
Висновок. Я ознайомилась з асимптотичними характеристиками складності та класами складності алгоритмів.
27.05.2014 22:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора