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

Перехід до торгівельного партнера Binance

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

ЗІ

Кафедра:

Не вказано

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

Рік:

2022

Тип роботи:

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

Предмет:

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

Завантажити

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

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №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:05-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись