ОЦІНКА СКЛАДНОСТІ АЛГОРИТМІВ. Звіт до лабораторної роботи з Програмування складних алгоритмів. Робота № 100341

ОЦІНКА СКЛАДНОСТІ АЛГОРИТМІВ

Інформація про навчальний заклад

ВУЗ:

Національний технічний університет України Київський політехнічний інститут

Інститут:

Не вказано

Факультет:

ЗІ

Кафедра:

Не вказано

Інформація про роботу

Рік:

2023

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Програмування складних алгоритмів

Завантажити

Частина тексту файла (без зображень, графіків і формул):

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

Звіт до лабораторної роботи Програмування складних алгоритмів

16.05.2023 12:15

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись