НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №1 з навчальної дисципліни “Програмування складних алгоритмів” Тема: ОЦІНКА СКЛАДНОСТІ АЛГОРИТМІВ Мета: Метою лабораторної роботи є отримання практичних навичок визначати часову складність алгоритму. Навчитися будувати алгоритми з мінімальною часовою складністю для вирішення поставлених задач. Теоретична частина Алгоритм – це скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату. Основними мірами обчислювальною складності алгоритмів є: Часова складність алгоритму в комп'ютерних науках є обчислювальною складністю алгоритму, яка описує час потрібний для виконання алгоритму. Вона зазвичай визначається шляхом підрахунку кількості елементарних операцій, виконуваних алгоритмом, при цьому вважають, що кожна елементарна операція виконується за фіксовану кількість часу. Таким чином, кількість часу і кількість елементарних операцій, необхідних для виконання алгоритму, відрізняються постійним множником. Ємнісна складність, яка характеризує пам'ять, необхідну для виконання алгоритму. Часова та ємнісна складність тісно пов'язані між собою. Обидві є функціями від розміру вхідних даних. Структурна складність - характеристика кількості керуючих структур в алгоритмі і специфіки їх взаємного розташування. Когнітивна складність - характеристика доступності алгоритму для розуміння фахівцями прикладних областей. Виділяють такі основні класи алгоритмів: логарифмічні: f(n) = O (log2n); лінійні: f(n) = O (n); поліноміальні: f(n) = O (nm); тут m - натуральне число, більше від одиниці; при m = 1 алгоритм є лінійним; експоненційні: f(n) = O (an); a - натуральне число, більше від одиниці. Для однієї й тієї ж задачі можуть існувати алгоритми різної складності. Часто буває і так, що більш повільний алгоритм працює завжди, а більш швидкий - лише за певних умов. Загальне завдання Сформувати двовимірний масив цілих чисел, використовуючи датчик випадкових чисел. Використати оголошення масиву на n елементів (кількість елементів задавати з екрану). Провести оцінку часової складності алгоритму, використовуючи О-символіку в найгіршому або/і в середньому. Порівняти час роботи та кількість ітерацій/кількість кроків роботи програми з різною розмірністю масиву (10x10, 50x50, 100x100, 500x500). Оцінку часу роботи навести у вигляді графіка, або таблиці. Завдання 1 / Завдання 2 / / Результат роботи Завдання 1  Розмір матриці n Кількість ітерацій Час виконання  10 120 - 220 8 мс  50 2600 - 5100 12 мс  100 10200 - 20200 14 мс  500 251000 - 501000 19 мс   Завдання 2  Розмір матриці n Кількість ітерацій Час виконання  10 40 <1 мс  50 700 <1 мс  100 2650 1 мс  500 63250 6 мс   Блок-схема / Завдання 1 / Завдання 2 / Висновок: було написано програму, що створює двовимірний масив, виконує певні зміни та заміряє час виконання алгоритму. Програму було досліджено на швидкість роботи та кількість ітерацій при виконуванні кожного завдання та при різних величинах масиву. Час виконання алгоритму було максимально мінімізовано. Програмний код import java.util.*; public class LR1 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("Введіть розмір масиву: "); int n = scanner.nextInt(); int[][] arr = new int[n][n]; System.out.println("Початковий масив"); for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { arr[i][j] = (int) (Math.random() * 50); System.out.print(arr[i][j] + "\t"); } System.out.println(); } System.out.println("Введіть номер завдання(1 або 2): "); n = scanner.nextInt(); if(n==1){ System.out.println("--------Завдання 1--------"); long firstTimeMills = System.currentTimeMillis(); int sum = 0, tempSum = 0; for(int i=0;i<arr.length;i++) sum= sum+arr[0][i]; System.out.println("Сума елементів першого стовпчика = "+sum); System.out.print("Рядки в яких сума елементів менше ніж сума елементів першого стовпчика: "); for(int i=0;i<arr.length;i++){ tempSum=0; for(int j=0;j<arr.length;j++){ tempSum=tempSum+arr[i][j]; } if(tempSum<sum) { System.out.print(i+1+" "); for (int j = 0; j < arr.length; j++) arr[i][j] = arr[i][j] + 5; } } firstTimeMills =System.currentTimeMillis() - firstTimeMills; System.out.println("\nМасив після перетворень першого завдання: "); for (int i = 0; i < arr.length; i++) { for (int j = 0; j< arr.length ; j++) System.out.print(arr[i][j] + "\t"); System.out.println(); } System.out.println("Швидкість виконання першого завдання: "+firstTimeMills + "ms"); } if(n==2) { System.out.println("--------Завдання 2--------"); long secondTimeMills = System.currentTimeMillis(); int count = 1, temp=0; for(int i=0;i<arr.length;i++){ for(int j=0;j+count<(arr.length)/2;j++){ temp=arr[i][j+count]; arr[i][j+count]=arr[i][arr.length-1-j-count]; arr[i][arr.length-1-j-count]=temp; } if(arr.length%2!=0) { if ((i + 1) * 2 <= arr.length) count++; else count--; } else{ if((i + 1) * 2 < arr.length) count++; else if((i + 1) * 2 != arr.length) count--; } } secondTimeMills = System.currentTimeMillis() - secondTimeMills; System.out.println("\nМасив після перетворень другого завдання: "); for (int i = 0; i < arr.length; i++) { for (int j = 0; j< arr.length ; j++) System.out.print(arr[i][j] + "\t"); System.out.println(); } System.out.println("Швидкість виконання другого завдання: "+secondTimeMills + "ms"); } if(n!=2 && n!=1) System.out.println("Введено невірне значення"); } }