Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 1 з дисципліни: “Алгоритми та методи обчислень” на тему: “Аналіз складності алгоритмів” Львів 2016 Мета роботи: оволодіти методикою аналізу складності основних алгоритмічних конструкцій. Навчитись обчислювати функцію трудомісткості. Ознайомитись з класифікацією алгоритмів на основі функції трудомісткості. Опанувати методику аналізу розроблених алгоритмів на предмет їх складності. Теоретичні відомості: Поняття алгоритму В старому трактуванні алгоритм - це точний набір інструкцій, що описують послідовність дій деякого виконавця для досягнення результату, рішення деякого завдання за кінцевий час. У зв'язку з розвитком паралельності в роботі комп'ютерів слово «послідовність» стали заміняти більше загальним словом «порядок». Це пов'язане з тим, що якісь дії алгоритму повинні бути виконані тільки один за одним, але якісь можуть бути й незалежними. Єдиного «правдивого» визначення поняття «алгоритм» немає. «Алгоритм - це всяка система обчислень, що виконуються по строго визначеним правилам, які після певного числа кроків свідомо приводять до рішення поставленого завдання.» (А. Колмогоров) «Алгоритм - це точне розпорядження, яке визначає обчислювальний процес, що йде від варійованих вихідних даних до шуканого результату.» (А. Марков) «Алгоритм - строго детермінована послідовність дій, що описує процес перетворення об'єкта з початкового стану в кінцеве, записана за допомогою зрозумілих виконавцеві команд.» (М. Угринович) Складність алгоритмів Для оцінки алгоритмів існує багато критеріїв. Найбільшу увагу приділяють порядку росту, необхідного для розв'язання задачі часу та розміру пам'яті при збільшені вхідних даних. З кожною конкретною задачею зв'язане число, яке називається розміром задачі і яке виражає міру кількості вхідних даних. Наприклад, розміром задачі множення матриць може бути найбільший розмір матриць-співмножників. Розміром задачі про графи може бути число ребер даного графа. Час, затрачений на обчислення при виконанні алгоритму, являє собою суму часів окремих виконаних операторів. Програму, написану на мові високого рівня, можна перетворити прямим ( хоча і не простим) шляхом в програму на машинному коді заданої ЕОМ. Це в принципі дає метод оцінки часу виконання вказаної програми, але такий підхід орієнтований на конкретну ЕОМ і не дає загальної залежності часу обчислення від розмірів задачі. В області аналізу та побудови алгоритмів прийнято виражати час виконання, як і будь-яку іншу міру ефективності, з точністю до мультиплікативної константи. Це, зазвичай, робиться шляхом підрахунку лише певних ключових операцій, виконаних алгоритмом (що легко здійснити, аналізуючи версію цього алгоритму, записану на мові високого рівня). Час, який витрачається алгоритмом, як функція розміру задачі, називається часовою складністю цього алгоритму. T(n). Асимптотику поведінки цієї функції при збільшенні розміру задачі називають асимптотичною часовою складністю, а для її позначення використовують нотацію Ландау (велике O). Аналогічно, можна виділити просторову складність та асимптотичну просторову складність. Виконання роботи: Варіант 12 Завдання: Продублювати всі непарні елементи заданої послідовності. Код програми, який реалізовує дану задачу: #include<iostream>; #include<list> using namespace std; int main() { setlocale(LC_CTYPE, "ukr"); std::list<int> t = std::list<int>{ 5, 6, 7, 67,34,22,98,45,00,5,3}; std::list<int> result = std::list<int>{}; cout << "Початковий список: " << endl<<endl; while (t.size()>0) { int ssh = t.front(); cout << ssh << " , "; t.pop_front(); result.push_front(ssh); if (ssh % 2 == 1) result.push_front(ssh); } cout <<endl<<endl<< "Кiнцевий список: " <<endl<< endl; while(result.size()>0) { int ssh = result.front(); cout << ssh << " , "; result.pop_front(); } cout << endl << endl; system("pause"); return 0; } Результат виконання програми: / Рис.1 Результат виконання програми Складність алгоритму: За трудомісткістю алгоритм належить до класу N (Numerical), оскільки залежить тільки від розмірності вхідних даних.
Висновок: На даній лабораторній роботі я ознайомилася та оволоділа методикою аналізу складності основних алгоритмічних конструкцій, навчилася обчислювати функцію трудомісткості, ознайомилася з класифікацією алгоритмів на основі функції трудомісткості та опанувала методику аналізу розроблених алгоритмів на предмет їх складності.