Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритм, властивості, параметри та характеристики складності алгоритму
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
ПЦБ
Кафедра:
Кафедра електронних обчислювальних машин
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритми та моделі обчислень
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Інститут комп’ютерних технологій, автоматики та метрології
кафедра “Електронних обчислювальних машин”
/
Звіт
з лабораторної роботи №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;
}
Екранна форма з результатами роботи програми:
ОБОВЯЗКОВО. ЗАПУСТІТЬ ПРОГРАМУ І ВСТАВТЕ СЮДА СКРІН. ЦЕ ЗРОБЛЕНО ДЛЯ ТОГО ЩОБ ЧАС БУВ У КОЖНОГО РІЗНИЙ !!!
Висновок:
В даній лабораторній роботі я навчився писати алгоритми на мові С++ і визначати складність алгоритму.
25.03.2025 11:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора