Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Асимптотичні характеристики складності алгоритму. Алгоритми з поліноміальною та експоненціальною складністю
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2014
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 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. графік функції трудомісткості
Висновок: в даній лабораторній роботі я оволодів методикою аналізу складності основних алгоритмічних конструкцій. Навчився обчислювати функцію трудомісткості. Ознайомився з класифікацією алгоритмів на основі функції трудомісткості. Опанував методику аналізу розроблених алгоритмів на предмет їх складності.
27.05.2014 22:54
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора