Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
СКЛАДНІСТЬ АЛГОРИТМУ
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №1
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
СКЛАДНІСТЬ АЛГОРИТМУ
Варіант №12
Київ 2022
Мета:
Метою лабораторної роботи є отримання практичних навичок визначати часову складність алгоритму. Навчитися будувати алгоритми з мінімальною часовою складністю для вирішення поставлених задач.
Теоретична частина
Алгоритм – це скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату.
Основними мірами обчислювальною складності алгоритмів є:
– часова складність, яка характеризує час, необхідний для виконання алгоритму на даній машині; цей час, як правило, визначається кількістю операцій, які потрібно виконати для реалізації алгоритму;
– ємнісна складність, яка характеризує пам’ять, необхідну для виконання алгоритму.
Часова та ємнісна складність тісно пов’язані між собою. Обидві є функціями від розміру вхідних даних.
Складність алгоритму описуватиметься функцією f(n), де n – розмір вхідних даних. Важливе теоретичне і практичне значення має класифікація алгоритмів, яка бере до увагу швидкість зростання цієї функції.
Найпоширеніші функції, які зустрічаються в аналізі алгоритмів, а саме:
O(1) – константа;
O(log n) – логарифмічне;
O(n) – лінійне;
O(n · log n) – лінеарітмічне;
O(n²) – квадратичне;
O(2ⁿ) – експоненціальне;
O(n!) – факторіальне;
де n → ∞.
O(1)
Незалежно від того, що ви згодовуєте алгоритму, він все одно працюватиме за той самий проміжок часу.
O(log n)
Час роботи алгоритму ледь збільшився при збільшенні вхідних даних.
O(n)
Час розрахунку збільшується з тією ж швидкістю, що і вхідні дані.
O(n²)
Час розрахунку збільшується зі швидкістю n².
O(n!)
Час роботи збільшується з темпами n!, тобто, якщо n дорівнює 5, це 5x4x3x2x1 або 120. Це не так вже й погано при малих значеннях n, але при великих значеннях алгоритм стає нереально обрахувати.
Розрахунок часової складності
Алгоритм 1
Розмір
Складність
Кількість ітерацій
Час виконання
10х10
O(n^2)
Квадратична складність
2862
16 нс
50х50
2189182
21 нс
34173682
27 нс
100х100
20937666752
711 нс
500х500
Алгоритм 2
Розмір
Складність
Кількість ітерацій
Час виконання
10х10
O(n^2)
Квадратична складність
3254
8 нс
50х50
6324174
27 нс
100х100
102581844
21 нс
500х500
81045860984
165 нс
Завдання:
Використовуючи алгоритми, згідно варіанту завдання, скласти програму розрахунку заданих величин та провести аналіз ефективності реалізованих алгоритмів.
Сформувати двовимірний масив цілих чисел, використовуючи датчик випадкових чисел. Використати оголошення масиву на n елементів (кількість елементів задавати з екрану). Провести оцінку часової складності алгоритму, використовуючи О-символіку в найгіршому або/і в середньому. Порівняти час роботи та кількість ітерацій/кількість к р о к і в р о б о т и п р о г р а м и з р із н о ю розмірністю масиву (10x10, 50x50, 100x100, 500x500). Оцінку часу роботи навести у вигляді графіка, або таблиці.
Використовуючи алгоритми, згідно варіанту завдання, скласти програму розрахунку заданих величин та провести аналіз ефективності реалізованих алгоритмів.
Завдання до Варіанту_12
Знайти стовпчик з найбільшою послідовністю елементів, впорядкованих за зростанням.
Провести обмін елементів матриці за вказаною схемою
Результати виконання лабораторної роботи:
Код:
//Лабораторна робота №1_ПСА
//ТР-15_Ткаченко_Майя, Варіант_12
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
void create_array(int n, int array[n][n]);
void display_array(int n, int array[n][n]);
void task1(int n, int array[n][n]);
void task2(int n, int array[n][n]);
int main(void)
{
printf("\n-----------------------------------------\n");
printf("<<<~~~ Завдання 1: Знайти стовпчик з найбільшою послідовністю елементів, впорядкованих за зростанням.\n");
printf("-----------------------------------------\n");
//визначаємо розмір масиву
printf("Введіть розмір масиву n :");
int n;
scanf("%d", &n);
//виведемо початковий масив
int array[n][n];
create_array(n, array);
display_array(n, array);
//вимірюємо час
clock_t t1;
t1 = clock();
//виконуємо завдання 1
task1(n, array);
printf("-----------------------------------------\n");
//кінець виміру часу
t1 = clock() - t1;
int time_taken1 = ((int)t1);
//вимірюємо час
clock_t t2;
t2 = clock();
printf("\n\n-----------------------------------------\n");
//виконуємо завдання 2
printf("<<<~~~ Завдання 2: Провести обмін елементів матриці за вказаною схемою варіанту (схему дивитися у звіті)\n");
printf("-----------------------------------------\n");
task2(n, array);
//кінець виміру часу
t2 = clock() - t2;
int time_taken2 = ((int)t2);
//виведемо результат другого завдання
display_array(n, array);
printf("\n-----------------------------------------\n\n");
printf("\n<<<----Oперації першого завдання зайняли %d наносекунд---->>>", time_taken1);
printf("\n<<<----Oперації другого завдання зайняли %d наносекунд---->>>", time_taken2);
return 0;
}
void create_array(int n, int array[n][n])
{
srand(time(NULL));
for (int i = 0; i<n;i++)
for (int j = 0; j<n;j++)
array[i][j] = (rand() % 100) - 50;
}
void display_array(int n, int array[n][n])
{
for (int i = 0; i<n;i++)
{
for (int j = 0; j<n;j++)
printf("%d\t", array[i][j]);
printf("\n");
}
}
void task1(int n, int array[n][n])
{
int index_of_column_with_max_subsequence = 0; //в цю змінну буде записуватися індекс стовпчика з найбільшою зростаючою послюдовністю
int max_subsequence = 0; //в цю змінну буде записуватися найбільшу зростаючу послюдовність
for (int j = 0; j < n; j++) //проходимо по кожному стовпчику, тому спочатку j, а потім i
{
int current_subsequence = 0; //лічильник для кожної послідовності в стовпчику
for (int i = 0; i < n - 1; i++)
{
if (array[i+1][j] >= array[i][j]) //якщо послідовнсть продовжує зростати
current_subsequence++;
if (current_subsequence > max_subsequence) //якщо поточна послідовнсть більша за максимальну, оновлюємо максимальну
{
max_subsequence = current_subsequence;
index_of_column_with_max_subsequence = j;
}
if (array[i+1][j] < array[i][j]) //якщо послідовність обірвалася, бо почала спадати
current_subsequence = 0;
}
}
printf("<====У стовпчику %d знаходиться найбільша послідовність елементів, впорядкованих за зростанням, а саме %d елементів підряд===>\n", index_of_column_with_max_subsequence+1, max_subsequence + 1);
}
void task2(int n, int array[n][n])
{
for (int i = 0; i < n; i++) //чиста алгоритміка, не знаю, як пояснювати
{
for (int j = n/2 + abs(i-n/2); j < n; j++) //abs(x) - абсолютне значення(модуль)
{
int temp = array[i][j];
array[i][j] = array[j][i];
array[j][i] = temp;
}
}
}
Посилання на Repl.it :
https://replit.com/join/jrzhxfxxke-tr-15tkachienko
Висновки
Під час виконання даної лабораторної роботи було розглянуто різні часові складності алгоритмів. Створено програму, яка виконує знаходить стовпчик з найбільшою послідовністю елементів впорядкованих за зростанням і переставляє елементи матриці згідно схеми до варіанту, час виконання алгоритму виводиться на екран.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора