Міністерство освіти і науки України Національний університет «Львівська політехніка» Кафедра ЕОМ / ЗВІТ З лабораторної роботи №1 з дисципліни: «Алгоритми та методи обчислень» на тему: «Алгоритм, властивості, параметри та характеристики складності алгоритму» Мета роботи: Оволодіти методикою аналізу складності основних алгоритмічних конструкцій. Навчитись обчислювати функцію трудомісткості. Ознайомитись з класифікацією алгоритмів на основі функції трудомісткості. Опанувати методику аналізу розроблених алгоритмів на предмет їх складності. Постановка задачі: Задано масив M(14). Знайти суму п’яти найменших елементів і поділити їх на суму всіх інших. Вивести вихідний масив, п’ять найменших елементів, суму всіх інших елементів та одержаний результат. Код програми: #include <iostream> using namespace std; float sum, sumin; double rez; int main() { setlocale(LC_ALL, "ukr"); int n = 14; cout<<"Введiть масив M[14]: "<< endl; int *M = new int[n]; for (int i = 0; i < n; ++i) { cin >> M[i]; } cout<<endl; cout<<"Ваш масив M[14]: "<<endl; for (int i = 0; i < n; i++) cout<< M[i]<<" "; cout << endl<<endl; for (int j = 0; j<n; j++) { for (int i = 0; i < n - 1; i++) { if (M[i] < M[i + 1]) { int tmp; tmp = M[i + 1]; M[i + 1] = M[i]; M[i] = tmp; } } } cout << "Масив M[14] вiдсортований по спаданню: " << endl; for (int i = 0; i < n; i++) cout << M[i] << " "; cout << endl << endl; for (int i = n - 1; i > n - 6; --i) { sum = sum + M[i]; } cout<< "Сума 5 найменших елеметiв: "<<endl; cout << sum << endl; for (int i = n - 6; i > n - 15; --i) { sumin = sumin + M[i]; } cout << endl; cout << "Сума iнших елементiв: "<< endl; cout << sumin << endl << endl; cout << "Одержаний результат: "<< endl; rez = sum/sumin; cout << rez << endl << endl; } Алгоритм розв’язання задачі (Блок-схема алгоритму): Дослідження складності алгоритму: Клас алгоритму - Клас N (Numerical) Функція трудомісткості алгоритму: int i, n = 14 , sum, sumin; 1 операція for (int i = n - 1; i > n - 6; --i) 1 операція, 5 проходів циклу { sum = sum + M[i]; 3 операції на кожний прохід циклу } for (int i = n - 6; i > n - 15; --i) 1 операція, 9 проходів циклу { sumin = sumin + M[i]; 3 операції на кожний прохід циклу } rez = sum/sumin; 2 операції Обчислення:
= 1 + 1 + 5*3 + 1 + 3*9 + 2 = 47 = O(1). Назва асимптотичного класу ефективності алгоритму – Константний Графік: / Рис.1. Графік функції трудомісткості/ Результат виконання програми: / Рис.2. Ескіз вікна виконання програми Висновок: В даній лабораторній роботі я оволодів методикою аналізу складності основних алгоритмічних конструкцій. Навчився обчислювати функцію трудомісткості. Ознайомився з класифікацією алгоритмів на основі функції трудомісткості. Опанував методику аналізу розроблених алгоритмів на предмет їх складності.