МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Лабораторна робота №2 на тему: "Параметри та характеристики складності алгоритму. " з дисципліни " Алгоритми та методи обчислень " Львів – 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.