Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Складність алгоритму
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2023
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №1
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «Складність алгоритму»
Варіант № 20
Дата «17» квітня 2022
Мета роботи:
Метою лабораторної роботи є отримання практичних навичок визначати часову складність алгоритму.
Навчитися будувати алгоритми з мінімальною часовою складністю для вирішення поставлених задач.
Завдання до лабораторної роботи
Сформувати двовимірний масив цілих чисел, використовуючи датчик випадкових чисел. Використати оголошення масиву на n елементів (кількість елементів задавати з екрану). Провести оцінку часової складності алгоритму, використовуючи О-символіку в найгіршому або/і в середньому. Порівняти час роботи та кількість ітерацій/кількість кроків роботи програми з різною розмірністю масиву (10x10, 50x50, 100x100, 500x500).
Оцінку часу роботи навести у вигляді графіка, або таблиці.
Завдання відповідно до варіанту
Завдання 1: В кожному рядку масиву всі від’ємні елементи перенести в ліву частину
Завдання 2: В кожному стовпчику кожен третій елемент знищити, змістивши на його місце нижні елементи.
Теоретичні відомості
Алгоритм – це скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату.
Складність алгоритму – це кількісна характеристика, що відображує споживані алгоритмом ресурси під час свого виконання. Основними ресурсами, що оцінюються, є час виконання і простір пам’яті.
Основними мірами обчислювальною складності алгоритмів є:
часова складність, яка характеризує час, необхідний для виконання алгоритму на даній машині; цей час, як правило, визначається кількістю операцій, які потрібно виконати для реалізації алгоритму;
ємнісна складність, яка характеризує пам’ять, необхідну для виконання алгоритму.
Часова та ємнісна складність тісно пов’язані між собою. Обидві є функціями від розміру вхідних даних.
В алгоритму є вхід - опис завдання, яке потрібно вирішити. На його розв’язання алгоритм витрачає певний час (тобто кількість операцій). Складність - це функція від довжини входу, значення якої дорівнює максимальному (за будь-якими входами даної довжини) кількості операцій, необхідних алгоритму для отримання відповіді.
Одним зі спрощених видів аналізу складності алгоритмів, що використовують при комп’ютерній їх реалізації, є асимптотичний аналіз алгоритмів. Він використовується з метою порівняння витрат часу та інших ресурсів різноманітними алгоритмами, призначеними для вирішення одного і того самого завдання. Зазвичай алгоритм, більш ефективний в асимптотичному сенсі, буде більш продуктивним для всіх вхідних даних, за винятком дуже маленьких.
Результати роботи для завдання 1
Написано програмний код, що виконує зсуву всіх від’ємних елементів кожного рядка двовимірного масиву в ліву частину. Для цього спочатку з консолі вводиться розмір масиву, після цього масив заповнюється генератором випадкових чисел та виводиться на екран. Далі масив перетворюється, виводиться час роботи алгоритму та масив в результаті обробки.
Алгоритм реалізовано за допомогою двох вкладених циклів, що завжди ітеруються від 0 до розміру масиву, тому складність алгоритму: N*N = O(N2)
/
Рисунок 1. Залежність часу виконання від розмірів масиву
/
Рисунок 2. Скріншот результату завдання 1
Результати роботи для завдання 2
Написано програмний код, що виконує видалення кожного третього елемента в кожному стовпчику та зсуву всіх наступних вгору. Спочатку з консолі вводиться розмір масиву, після цього масив заповнюється генератором випадкових чисел та виводиться на екран. Далі масив перетворюється, виводиться час роботи алгоритму та масив в результаті обробки.
Так як відбувається взаємодія лише з рядками і немає потреби ітеруватись по горизонталі, алгоритм можна реалізувати лінійним алгоритмом O(n).
Для виконання завдання відбувається створення нового масиву з меншою кількістю рядків та перезапис з введеного масиву всіх рядків, крім кожного третього.
/
Рисунок 3. Залежність часу виконання від розмірів масиву
/
Рисунок 4. Скріншот результату завдання 2
Висновки
У процесі виконанні лабораторної роботи було отримано практичні навички визначення часової складності алгоритму та побудови алгоритмів з мінімальною часовою складністю для вирішення поставлених задач.
Код програми
Завдання 1
// Lab_1 task1
#include <iostream>
#include <ctime>
#include <chrono>
#include <iomanip>
int main()
{
int size;
std::cout << "Введіть розмірність матриці:" << std::endl;
std::cin >> size;
std::cout << "\nПочаткова матриця:";
int** arr = new int* [size];
srand(time(NULL));
for (int i = 0; i < size; i++) {
arr[i] = new int[size];
std::cout << std::endl;
for (int j = 0; j < size; j++) {
arr[i][j] = rand() % 201 - 100;
std::cout << std::setw(4) << arr[i][j] << " ";
}
}
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < size; i++) {
int num = 0;
for (int j = 0; j < size; j++) {
if (arr[i][j] < 0) {
if (j != num) {
int temp = arr[i][j];
arr[i][j] = arr[i][num];
arr[i][num] = temp;
}
num++;
}
}
}
std::chrono::duration<double, std::milli> time = std::chrono::high_resolution_clock::now() - start;
std::cout << "\n\nЧас виконання:" << time.count() << "ms\n";
std::cout << "\nРезультат:";
for (int i = 0; i < size; i++) {
std::cout << "\n";
for (int j = 0; j < size; j++)
std::cout << std::setw(4) << arr[i][j] << " ";
}
}
Завдання 2
//Lab_1 task2
#include <iostream>
#include <ctime>
#include <chrono>
#include <iomanip>
#include <tgmath.h>
int main()
{
int size;
std::cout << "Введіть розмірність матриці:" << std::endl;
std::cin >> size;
std::cout << "\nПочаткова матриця:";
int** arr = new int* [size];
srand(time(NULL));
for (int i = 0; i < size; i++) {
arr[i] = new int[size];
std::cout << std::endl;
for (int j = 0; j < size; j++) {
arr[i][j] = rand() % 201 - 100;
std::cout << std::setw(4) << arr[i][j] << " ";
}
}
std::cout << "\n\n";
int m1;
m1 = size - (size / 3);
int** arr1 = new int* [m1];
srand(time(NULL));
for (int i = 0; i < m1; i++)
arr1[i] = new int[size];
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < m1; i++) {
int needed_index = (int)((1.0 / 4.0) * (6 * i + pow(-1, i) - 1));
arr1[i] = arr[needed_index];
}
std::chrono::duration<double, std::milli> time = std::chrono::high_resolution_clock::now() - start;
std::cout << "Час виконання: " << time.count() << "ms\n";
std::cout << "\nРезультат:";
for (int i = 0; i < m1; i++) {
std::cout << "\n";
for (int j = 0; j < size; j++)
std::cout << std::setw(4) << arr1[i][j] << " ";
}
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора