Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра ЕОМ / Звіт з лабораторної роботи № 2 з дисципліни: «Алгоритми та методи обчислень» на тему: “Асимптотичні характеристики складності алгоритму. Алгоритми з поліноміальною та експоненціальною складністю” Мета роботи: Оволодіти методикою аналізу складності основних алгоритмічних конструкцій. Навчитись обчислювати функцію трудомісткості. Ознайомитись з класифікацією алгоритмів на основі функції трудомісткості. Опанувати методику аналізу розроблених алгоритмів на предмет їх складності. Постановка задачі: У заданій матриці вибрати в кожному рядку елемент з найменшим значенням, а потім серед цих чисел вибрати найбільше. Вивести задану матрицю, мінімальні елементи кожного рядка, найбільший елемент з них та його індекси. Алгоритм розв’язання задачі: #include <iostream> using namespace std; int main() { int N; cout<<"SIZE MATRIX"<<endl; cin>>N; cout<<"ELEMENTS"<<endl; int arr[100][100]; int ret[100]; int m; for(int i=0; i<N; i++) { for(int j=0; j<N; j++) cin>>arr[i][j]; } cout<<"MATRIX"<<endl; for(int i=0; i<N; i++) { for(int j=0; j<N; j++) cout<<arr[i][j]<<" "; cout<<endl; } cout<<"MIN"<<endl; for(int i=0; i<N; i++) { ret[i]=arr[i][0]; for(int j=0; j<N; j++) {if(arr[i][j]<ret[i]) ret[i]=arr[i][j];} cout<<ret[i]<<" "; } cout<<endl; m=ret[0]; for(int i=1; i<N; i++) { if(ret[i]>m) m=ret[i]; } cout<<"MAX of MIN"<<endl<<m<<endl; cout<<"INDEXES"<<endl; for(int i=0; i<N; i++) { for(int j=0; j<N; j++) if(arr[i][j]==m) cout<<i+1<<" "<<j+1<<endl; } } Результат роботи: / Рис.1. Ескіз вікна з результатом виконання програми Клас алгоритму - N (Numerical) Функція трудомісткості алгоритму
Назва асимптотичного класу ефективності алгоритму – лінійний. / Рис.1. графік функції трудомісткості Висновок: в даній лабораторній роботі я оволодів методикою аналізу складності основних алгоритмічних конструкцій. Навчився обчислювати функцію трудомісткості. Ознайомився з класифікацією алгоритмів на основі функції трудомісткості. Опанував методику аналізу розроблених алгоритмів на предмет їх складності.