НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №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 Висновки Під час виконання даної лабораторної роботи було розглянуто різні часові складності алгоритмів. Створено програму, яка виконує знаходить стовпчик з найбільшою послідовністю елементів впорядкованих за зростанням і переставляє елементи матриці згідно схеми до варіанту, час виконання алгоритму виводиться на екран.