НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №1 з навчальної дисципліни “Програмування складних алгоритмів” Тема: ОЦІНКА СКЛАДНОСТІ АЛГОРИТМІВ Варіант 13 Київ 2022 Мета: Метою лабораторної роботи є отримання практичних навичок визначати часову складність алгоритму. Навчитися будувати алгоритми з мінімальною часовою складністю для вирішення поставлених задач. Теоретична частина Алгоритм – це скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату. Основними мірами обчислювальною складності алгоритмів є: – часова складність, яка характеризує час, необхідний для виконання алгоритму на даній машині; цей час, як правило, визначається кількістю операцій, які потрібно виконати для реалізації алгоритму; – ємнісна складність, яка характеризує пам’ять, необхідну для виконання алгоритму. Часова та ємнісна складність тісно пов’язані між собою. Обидві є функціями від розміру вхідних даних. Надалі обмежимося тільки аналізом часової складності. Складність алгоритму описується функцією О(п), де п – розмір вхідних даних. Важливе теоретичне і практичне значення має класифікація алгоритмів, яка бере до увагу швидкість зростання цієї функції. Завдання 1 Сформувати двовимірний масив цілих чисел, використовуючи датчик випадкових чисел. Використати оголошення масиву на n елементів (кількість елементів задавати з екрану). Провести оцінку часової складності алгоритму, використовуючи О-символіку в найгіршому або/і в середньому. Порівняти час роботи та кількість ітерацій/кількість к р о к і в р о б о т и п р о г р а м и з р і з н о ю розмірністю масиву (10x10, 50x50, 100x100, 500x500). Оцінку часу роботи навести у вигляді графіка, або таблиці. Завдання варіанту:
Завдання 2

Результат роботи Завдання 1 Розмір матриці n К-сть ітерацій Час виконання  10 110 11 мс  50 2550 11 мс  100 10100 13 мс  500 250500 12 мс   Завдання 2 Розмір матриці n К-сть ітерацій Час виконання  10 ~50 <1 мс  50 ~1250 <1 мс  100 ~50000 <1 мс  500 ~125000 3 мс  
Програмний код public class Lr1 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("Введіть розмірнісь масиву n"); int n = scanner.nextInt(); int[][] array = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { array[i][j] = (int)(Math.random() * 40) - 20; } System.out.println("Заповнений масив"); for (int i = 0; i < n; i++) { for (int j = 0; j< n ; j++) System.out.print(array[i][j] + "\t\t"); System.out.println(); } //task 1 System.out.println("Завдання 1"); long time = System.currentTimeMillis(); int[] results = new int[n]; for (int i = 0; i<n; i++) { int maxValue = 0; int currentValue = 0; for (int j = 1; j<n; j++) { if (array[i][j] < array[i][j-1]) { currentValue++; } else if (currentValue != 0) { if (currentValue + 1 > maxValue) maxValue = currentValue + 1; currentValue = 0; } } if (currentValue != 0 && currentValue + 1 > maxValue) maxValue = currentValue + 1; results[i] = maxValue; } int maxResultIndex = 0; for (int i = 1; i < n; i++) { if (results[i] > results[maxResultIndex]) maxResultIndex = i; } System.out.println("Pядок '" + (maxResultIndex + 1) + "' містить найбільшу послідовність елементів," + " впорядкованих за спаданням (" + results[maxResultIndex] + " елементів, що спадають)."); System.out.println(System.currentTimeMillis() - time + "ms"); //task 2 System.out.println("\nЗавдання 2"); time = System.currentTimeMillis(); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { int temp = array[i][j]; array[i][j] = array[j][i]; array[j][i] = temp; } } long final_time = System.currentTimeMillis() - time; System.out.println("Масив після перетворень (перекидання елементів масиву через головну діагональ)"); for (int i = 0; i < n; i++) { for (int j = 0; j< n ; j++) System.out.print(array[i][j] + "\t\t"); System.out.println(); } System.out.println(final_time + "ms"); } } Висновки: розроблено програму, що виконує два алгоритми, на прикладі яких закріплено знання щодо складності алгоритмів та підрахунку часу виконання алгоритму.