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

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

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

ВУЗ:

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

Інститут:

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

Факультет:

ПЦБ

Кафедра:

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

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

Рік:

2025

Тип роботи:

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

Предмет:

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

Група:

КІ

Завантажити

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

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

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

Borusu1

25.03.2025 11:05

Коментарі

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

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

поділитись