Алгоритм, властивості, параметри та характеристики складності алгоритму. Звіт до лабораторної роботи з Алгоритми та моделі обчислень. Робота № 101002

Алгоритм, властивості, параметри та характеристики складності алгоритму

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

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Інститут комп’ютерних технологій, автоматики та метрології

Факультет:

ПЦБ

Кафедра:

Кафедра електронних обчислювальних машин

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

Рік:

2025

Тип роботи:

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

Предмет:

Алгоритми та моделі обчислень

Група:

КІ

Завантажити

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Інститут комп’ютерних технологій, автоматики та метрології кафедра “Електронних обчислювальних машин” / Звіт з лабораторної роботи №1 дисципліни «Алгоритми та моделі обчислень» на тему: «Алгоритм, властивості, параметри та характеристики складності алгоритму» Варіант 3 Львів – 2024 ЛАБОРАТОРНА РОБОТА №1 Алгоритм, властивості, параметри та характеристики складності алгоритму Мета роботи: Проаналізувати складність заданих алгоритмів Завдання Скласти програму (С/C++), яка дозволяє провести порівняння двох алгоритмів за характеритикою часової складності. Вхідні дані: Варіант Алгоритм 1 Алгоритм 2 3 Сортування бульбашкою Сортування Шелла Алгоритм рішення завдання: Рішення алгоритму сортування бульбашкою Почати з першого елементу масива і порівняти його з попереднім елементом. Якщо поточний елемент мешний менший за попередній, то їх потрібно поміняти місцями. Повторювати цей процес для кожної пари сусідніх елементів у масиві Протовжувати цей процес до тих пір, поки весь масив не буде відсортований (тобто до тих пір, поки під час однієї ітерації не відбудеться жодного обміну елементів) Складність алгоритму: N2 Рішення алгоритму сортування Шелла Виберіть діапазон розмірів кроків, тобто середину масиву Для кожного кроку, починаючи з найбільшого, ітерувати через елементи масиву та виконувати вставне сортування з відповідним кроком Зменшувати крок і повторувати крок 2 до тих пір, поки крок не стане 1 Складність алгоритму: N2 Код програми: #include <iostream> #include <chrono> using namespace std; void babbleSort(int array[], int size){ for (int i = 0; i < size; i++) { for (int j = 1; j < size - i; j++) { if (array[j] < array[j - 1]) { int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } } void shellSort(int array[], int size){ for(int i = size / 2; i > 0; i /= 2){ for(int j = i; j < size; j++){ for(int k = j - i; k >= 0; k -= i){ if(array[k] > array[k + i]){ int temp = array[k]; array[k] = array[k + i]; array[k + i] = temp; } } } } } int main() { const int SIZE_ARR = 1000; int arr1[SIZE_ARR]; int arr2[SIZE_ARR]; int size = SIZE_ARR; srand(time(NULL)); for(int i = 0; i < size; i++) { int random = rand(); arr1[i] = random; arr1[i] = random; } auto startBubbleSort = std::chrono::high_resolution_clock::now(); babbleSort(arr1, size); auto endBubbleSort = std::chrono::high_resolution_clock::now(); auto durationBubbleSort = std::chrono::duration_cast<std::chrono::microseconds>(endBubbleSort - startBubbleSort); cout << "Time for bubble sort: " << durationBubbleSort.count() << " ms" << endl; auto startShellSort = std::chrono::high_resolution_clock::now(); shellSort(arr2, size); auto endShellSort = std::chrono::high_resolution_clock::now(); auto durationShellSort = std::chrono::duration_cast<std::chrono::microseconds>(endShellSort - startShellSort); cout << "Time for shell sort: " << durationShellSort.count() << " ms" << endl; return 0; } Екранна форма з результатами роботи програми: ОБОВЯЗКОВО. ЗАПУСТІТЬ ПРОГРАМУ І ВСТАВТЕ СЮДА СКРІН. ЦЕ ЗРОБЛЕНО ДЛЯ ТОГО ЩОБ ЧАС БУВ У КОЖНОГО РІЗНИЙ !!! Висновок: В даній лабораторній роботі я навчився писати алгоритми на мові С++ і визначати складність алгоритму.

Звіт до лабораторної роботи Алгоритми та моделі обчислень

Borusu1

25.03.2025 11:07

Коментарі

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

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

поділитись