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

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

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

ВУЗ:

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

Інститут:

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

Факультет:

ПЦБ

Кафедра:

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

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

Рік:

2025

Тип роботи:

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

Предмет:

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

Група:

КІ

Завантажити

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Інститут комп’ютерних технологій, автоматики та метрології кафедра “Електронних обчислювальних машин” / Звіт з лабораторної роботи №1 дисципліни «Алгоритми та моделі обчислень» на тему: «Алгоритм, властивості, параметри та характеристики складності алгоритму» Варіант 2 Львів – 2024 ЛАБОРАТОРНА РОБОТА №1 Алгоритм, властивості, параметри та характеристики складності алгоритму Мета роботи: Проаналізувати складність заданих алгоритмів Завдання Скласти програму (С/C++), яка дозволяє провести порівняння двох алгоритмів за характеритикою часової складності. Вхідні дані: Варіант Алгоритм 1 Алгоритм 2 2 Сортування бульбашкою Сортування включенням Алгоритм рішення завдання: Рішення алгоритму сортування бульбашкою Почати з першого елементу масива і порівняти його з попереднім елементом. Якщо поточний елемент мешний менший за попередній, то їх потрібно поміняти місцями. Повторювати цей процес для кожної пари сусідніх елементів у масиві Протовжувати цей процес до тих пір, поки весь масив не буде відсортований (тобто до тих пір, поки під час однієї ітерації не відбудеться жодного обміну елементів) Складність алгоритму: N2 Рішення алгоритму сортування включенням Починаючи з другого елемента масиву, порівняти його з попередніми елементами. Якщо поточний елемент менший за попередній, то вставте його місце у відсортованій частині масиву, зсунувши всі більші елементи на одну позицію вправо. Повторюйте цей процес для кожного елемента масиву. Продовжуйте цей процес до тих пір, поки не буде відсортована для послідовність. Складність алгоритму: 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 insertionSort(int array[], int size){ for(int i = 1; i < size; i++){ int curr = array[i]; int j = i - 1; while(j >= 0 && array[j] > curr){ array[j + 1] = array[j]; j--; } array[j + 1] = curr; } } 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 startInsertionSort = std::chrono::high_resolution_clock::now(); insertionSort(arr2, size); auto endInsertionSort = std::chrono::high_resolution_clock::now(); auto durationInsertionSort = std::chrono::duration_cast<std::chrono::microseconds>(endInsertionSort - startInsertionSort); cout << "Time for insertion sort: " << durationInsertionSort.count() << " ms" << endl; return 0; } Екранна форма з результатами роботи програми: ОБОВЯЗКОВО. ЗАПУСТІТЬ ПРОГРАМУ І ВСТАВТЕ СЮДА СКРІН. ЦЕ ЗРОБЛЕНО ДЛЯ ТОГО ЩОБ ЧАС БУВ У КОЖНОГО РІЗНИЙ !!! Висновок: В даній лабораторній роботі я навчився писати алгоритми на мові С++ і визначати складність алгоритму.

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

Borusu1

25.03.2025 11:06

Коментарі

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

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

поділитись