Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» ЗВІТ до лабораторної роботи № 1 з дисципліни «Програмування складних алгоритмів» Тема «Оцінка складності алгоритмів» Варіант № 24 Дата «12» лютого 2022 Лабораторна робота № 1: Мета роботи: Метою лабораторної роботи є отримання практичних навичок визначати часову складність алгоритму. Навчитися будувати алгоритми з мінімальною часовою складністю для вирішення поставлених задач. Завдання до роботи Сформувати двовимірний масив цілих чисел, використовуючи випадкові числа. Провести оцінку часової складності алгоритму, використовуючи О-символіку в найгіршому або/і в середньому. Порівняти час роботи та кількість ітерацій/кількість кроків роботи програми з різною розмірністю масиву (10*10, 50*50, 100*100). Оцінку часу роботи навести у вигляді графіка, або таблиці. Завдання відповідно до варіанту: Завдання 1 24 Поставити на головну діагональ матриці мінімальний елемент стовпчика   Завдання 2 24 Якщо в рядку від’ємних елементів більше ніж додатних, циклічно зсунути елементи рядка вліво на 1 елемен   1.2. Теоретичні відомості Складність алгоритму в комп'ютерних науках є обчислювальною складністю алгоритму, яка описує час потрібний для виконання алгоритму. Вона зазвичай визначається шляхом підрахунку кількості елементарних операцій, виконуваних алгоритмом, при цьому вважають, що кожна елементарна операція виконується за фіксовану кількість часу. Таким чином, кількість часу і кількість елементарних операцій, необхідних для виконання алгоритму, відрізняються постійним множником. Оцінка складності Складність алгоритмів зазвичай оцінюють за часом виконання або по використовуваній пам’яті. В обох випадках складність залежить від розмірів вхідних даних: масив з 100 елементів буде оброблений швидше, ніж аналогічний з 1000. При цьому мова йде не про точний час обчислень, який залежить від процесора, типу даних, мови програмування тощо. Оцінюється складність при прагненні розміру вхідних даних до нескінченності. При цьому вважають, що кожна елементарна операція виконується за однаковий час. Часову складність оцінюють для найгіршого випадку і визначають як максимальний час, необхідний для обробки алгоритмом будь-якої множини з n елементів. Часова складність алгоритму зазвичай визначається виразом O (f (n)) (або так званої О—нотації).  Вираз O(f(n)) означає, що час виконання алгоритму зростає з тією ж швидкістю, що і функція  f (n). Поширені складності алгоритмів • O(n) • O(n2) • O(n log2n) • O(2n) Приклад: Розглянемо код, який для масиву A[n, n]  знаходить максимальний елемент у кожному рядку. Розв’язання for i:=1 to N do   begin    max:=A[i,1];    for j:=1 to N do           if A[i,j]>max then  max:=A[i,j]    writeln(max);  end; У цьому алгоритмі змінна і змінюється від 1 до  n. При кожній зміні і, змінна j теж змінюється від 1 до  n. Під час кожної з  n ітерацій зовнішнього циклу, внутрішній цикл теж виконується  n раз. Загальна кількість ітерацій внутрішнього циклу дорівнює  n* n. Це визначає складність алгоритму O(n^2). 1.3. Результати роботи Завдання 1. Написано програмний код, який реалізує задачу поставити на головну діагональ матриці мінімальний елемент стовпчика. Спочатку з консолі задається розмір масиву. Після цього масив заповнюється генератором випадкових чисел та виводиться на екран. Далі масив перетворюється, виводиться час і виводиться час роботи програми. Алгоритм реалізовано за допомогою двох вкладених циклів, що завжди ітеруються від 0 до розміру масиву, тому складність алгоритму: N*N = O(N2) Розмір масиву Ітерації Час виконання  10x10 100 4.6ms  50x50 2500 54ms  100x100 10000 211ms  Нижче в таблиці представлено залежність часу виконання від розмірів масиву та відповідно кількості ітерацій. Завдання 2. Написано програмний код, який реалізує задачу, якщо в рядку від’ємних елементів більше ніж додатних, циклічно зсунути елементи рядка вліво на 1 елемент. Після цього масив заповнюється генератором випадкових чисел та виводиться на екран. Далі масив перетворюється, виводиться час і виводиться час роботи програми. Алгоритм реалізовано за допомогою двох вкладених циклів, що завжди ітеруються від 0 до розміру масиву, тому складність алгоритму: N*N = O(N2) Нижче в таблиці представлено залежність часу виконання від розмірів масиву та відповідно кількості ітерацій. Розмір масиву Ітерації Час виконання  10x10 100 4.8ms  50x50 2500 51ms  100x100 10000 234ms   1.4. Висновки по роботі При виконанні лабораторної роботи №1 було отримано практичні навички визначення часової складності алгоритму. Порівняно час роботи та кількість ітерацій роботи програми з різною розмірністю масиву. 1.5. Лістинг програми package Algoritm.ua; import java.util.Scanner; import java.util.concurrent.atomic.AtomicLong; public class Main { public static void main(String[] args) { System.out.print("Enter a number of the task you want to see(1-2):"); Scanner scan = new Scanner(System.in); int task = scan.nextInt(); System.out.println("Choose array size(1-4)"); System.out.println("1. 10✕10"); System.out.println("2. 50✕50"); System.out.println("3. 100✕100"); int sizeArray = scan.nextInt(); if (task == 1) { if (sizeArray == 1) { int[][] array1 = new int[10][10]; initialization(array1); System.out.println("\nRedacted"); AtomicLong time = new AtomicLong(System.nanoTime()); executionTask1(array1); printArray(array1); time.set(System.nanoTime() - time.get()); System.out.printf("Elapsed %,9.3f ms\n",time.get()/ 1_000_000.0); } if (sizeArray == 2) { int[][] array2 = new int[50][50]; initialization(array2); System.out.println("\nRedacted"); long time = System.nanoTime(); executionTask1(array2); printArray(array2); time = System.nanoTime() - time; System.out.printf("Elapsed %,9.3f ms\n", time / 1_000_000.0); } if (sizeArray == 3) { int[][] array3 = new int[100][100]; initialization(array3); System.out.println("\nRedacted"); long time = System.nanoTime(); executionTask1(array3); printArray(array3); time = System.nanoTime() - time; System.out.printf("Elapsed %9.3f ms\n", time / 1_000_000.0); } } public static void printArray(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[0].length; j++) { System.out.printf("%3d", arr[i][j]); } System.out.println(); } } public static void initialization(int[][] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[0].length; j++) { array[i][j] = (int) (Math.random() * 20) - 10; System.out.printf("%3d", array[i][j]); } System.out.println(); } } public static void executionTask1(int[][] array) { for (int j = 0, i = 0; j < array[0].length; j++, i++) { int min = array[i][j]; for (int k = 0; k < array.length; k++) { if (array[k][j] < min) { min = array[k][j]; array[k][j] = array[i][j]; array[i][j] = min; } } } } } Результат виконання: / Завдання 2. package Algoritm.ua; import java.util.Scanner; import java.util.concurrent.atomic.AtomicLong; public class Main { public static void main(String[] args) { System.out.print("Enter a number of the task you want to see(1-2):"); Scanner scan = new Scanner(System.in); int task = scan.nextInt(); System.out.println("Choose array size(1-4)"); System.out.println("1. 10✕10"); System.out.println("2. 50✕50"); System.out.println("3. 100✕100"); int sizeArray = scan.nextInt(); if (task == 2) { if (sizeArray == 1) { int[][] array4 = new int[10][10]; initialization(array4); System.out.println("\nRedacted"); long time = System.nanoTime(); executionTask2(array4); printArray(array4); time = System.nanoTime() - time; System.out.printf("Elapsed %9.3f ms\n", time / 1_000_000.0); } if (sizeArray == 2) { int[][] array4 = new int[50][50]; initialization(array4); System.out.println("\nRedacted"); long time = System.nanoTime(); executionTask2(array4); printArray(array4); time = System.nanoTime() - time; System.out.printf("Elapsed %9.3f ms\n", time / 1_000_000.0); } if (sizeArray == 3) { int[][] array4 = new int[100][100]; initialization(array4); System.out.println("\nRedacted"); long time = System.nanoTime(); executionTask2(array4); printArray(array4); time = System.nanoTime() - time; System.out.printf("Elapsed %9.3f ms\n", time / 1_000_000.0); } } public static void executionTask2(int[][] array){ for (int i = 0; i < array.length; i++) { int counter = 0; for (int j = 0; j < array[0].length; j++) { if (array[i][j] < 0) counter--; if (array[i][j] > 0) counter++; } if (counter < 0) { int tp = array[i][0]; for (int j = 0; j < array[0].length - 1; j++) { array[i][j] = array[i][j + 1]; } array[i][9] = tp; } } } public static void printArray(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[0].length; j++) { System.out.printf("%3d", arr[i][j]); } System.out.println(); } } public static void initialization(int[][] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[0].length; j++) { array[i][j] = (int) (Math.random() * 20) - 10; System.out.printf("%3d", array[i][j]); } System.out.println(); } } } Результат виконання: /