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