Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Параметри та характеристики складності алгоритму.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи оптимізації
Група:
КI
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Лабораторна робота №2
на тему: "Параметри та характеристики складності алгоритму. "
з дисципліни " Алгоритми та методи обчислень "
Виконав:
студент групи КІ – 3
Львів – 2008
Мета роботи : Аналіз впливу параметрів алгоритму на характеристики складності алгоритму.
Теоретичні відомості :
Алгоритм – це будь-який регулярний обчислювальний процес, що дозволяє за кінцеву кількість кроків розв’язувати задачі визначеного класу.
Алгоритм – це процес послідовної побудови величин, які проходять в дискретному часі таким чином, що в пчатковий момент часу задається початкова скінчена система величин, а кожний наступний момент системи величин отримується за певним законом.
Властивості алгоритму :
дискретність
масовість
детермінованість
елементарність
спрямованість
3. Параметри :
Система початкових даних
Система проміжних результатів
Система кінцевих результатів
Правило початку
Правило безпосереднього перероблення
Правило закінчення
Правило вводу
Правило виводу
Практична частина :
1. Знаходження НСД двох чисел методом перебору, починаючи з 1:
12 : 1 = 12 18 : 1 = 18
12 : 2 = 6 18 : 2 = 3
12 : 3 = 4 18 : 3 = 6
12 : 4 = 3 18 : 4 = 2
Часова складність: 8
2. Знаходження НСД двох чисел методом перебору, починаючи з меншого числа:
18 : 12 = 7 (4) 12 : 12 = 1
18 : 11 = 8 (4) 12 : 11 = 1 (1)
18 : 10 = 10 12 : 10 = 1 (2)
18 : 9 = 12 12 : 9 = 1 (3)
18 : 8 = 15 12 : 8 = 2
18 : 7 = 7 (4) 12 : 7 = 1
18 : 6 = 8 (4) 12 : 6 = 1 (1)
18 : 5 = 10 12 : 5 = 1 (2)
18 : 4 = 12 12 : 4 = 1 (3)
18 : 3 = 15 12 : 3 = 2
Часова складність: 5
3. Знаходження НСД двох чисел алгоритмом Евкліда:
60 : 8 = 7 (4)
8 : 4 = 2
Часова складність: 2
Висновок: дослідивши 3 методи знаходження НСД чисел в діапазоні від 1 до 100, я вияснив що середня часова складність цих алгоритмів така: для методу перебору, починаючи з 1 ≈ 36,2927; для методу перебору, починаючи з меншого числа ≈ 31,2367; для алгоритму Евкліда ≈ 2,4731. Результати дослідження середнього значення часової складності наведені згідно роботи програми обчислення НСД з перебором 10000 комбінацій чисел в діапазоні від 1 до 100.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора