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