Лабораторная работа по «Алгоритму и структуре данных»
Автор: SiriRise • Май 14, 2023 • Лабораторная работа • 791 Слов (4 Страниц) • 141 Просмотры
Ульяновский государственный технический университет
Факультет информационных систем и технологий
Кафедра «Измерительно-вычислительные комплексы»
Дисциплина «Алгоритмы и структуры данных»
Лабораторная работа №5
Вариант №22
Выполнил: студент группы ИСТбд-11
Орешин Д.Ю.
Проверил: преподаватель
Шишкин В.В.
Ульяновск
2023
Задача
Задана рекуррентная функция. Область определения функции – натуральные числа. Написать программу сравнительного вычисления данной функции рекурсивно и итерационно. Определить границы применимости рекурсивного и итерационного подхода. Результаты сравнительного исследования времени вычисления представить в табличной и графической форме.
Функция: F(1) = 1, F(2) = 1, F(n) = F(n-2)*(n-1), при n > 2
Сравнительный график для n от 1 до 1996 с шагом 50
Как мы видим из графика, рекурсивный подход работает прочти в два раза быстрее, чем итерационный. Но рекурсия перестает работать на проверяемом устройстве, если n больше 1996. При помощи модуля «sis» мы можем увеличить это значение до 4262. В то же время, итерационный подход может работать при n больше 100000. [pic 1]
Таким образом, границы применения рекурсивного подхода ограничиваются только характеристиками вычислительной машины. Итерационный подход, ограничен характеристиками вычислительной машины в меньшей степени, так как сохраняет эффективность и работу при больших числах. Программа не перестает работать, так как пространственная сложность константа, но начинает замедляться, соответственно время и является главным ограничением по применимости. Если наше время не ограничено, то программа может работать настолько долго, сколько ей требуется для расчета результата.
График итерационного подхода для n от 1 до 100000 с шагом 1000
[pic 2]
Сравнительная таблица для натуральных чисел от 1 до 1996 с шагом 50
N | Время рекурсии | Время итерации | Значение рекурсии | Значение итерации |
1 | 0.0000021 | 0.0000028 | 1 | 1 |
51 | 0.0000074 | 0.0000096 | 52046984.. | 52046984.. |
101 | 0.0000091 | 0.0000176 | 34243224.. | 34243224.. |
151 | 0.0000129 | 0.0000270 | 93726284.. | 93726284.. |
201 | 0.0000163 | 0.0000360 | 11830503.. | 11830503.. |
251 | 0.0000215 | 0.0000455 | 80080230.. | 80080230.. |
301 | 0.0000272 | 0.0000651 | 81544140.. | 81544140.. |
351 | 0.0000323 | 0.0000667 | 53850432.. | 53850432.. |
401 | 0.0000371 | 0.0000777 | 12673243.. | 12673243.. |
451 | 0.0000430 | 0.0000883 | 67904602.. | 67904602.. |
501 | 0.0000481 | 0.0001003 | 58490496.. | 58490496.. |
551 | 0.0000527 | 0.0001123 | 61326047.. | 61326047.. |
601 | 0.0000627 | 0.0001251 | 62345016.. | 62345016.. |
651 | 0.0000681 | 0.0001443 | 50848396.. | 50848396.. |
701 | 0.0000745 | 0.0001500 | 28344754.. | 28344754.. |
751 | 0.0000811 | 0.0001631 | 94133701.. | 94133701.. |
801 | 0.0000864 | 0.0001857 | 16535313.. | 16535313.. |
851 | 0.0000926 | 0.0002537 | 13843891.. | 13843891.. |
901 | 0.0001061 | 0.0002090 | 50395180.. | 50395180.. |
951 | 0.0001110 | 0.0002271 | 73510019.. | 73510019.. |
1001 | 0.0001204 | 0.0002500 | 39939844.. | 39939844.. |
1051 | 0.0001275 | 0.0002629 | 75686345.. | 75686345.. |
1101 | 0.0001380 | 0.0002819 | 47135581.. | 47135581.. |
1151 | 0.0003579 | 0.0005479 | 91394046.. | 91394046.. |
1201 | 0.0002031 | 0.0003425 | 52515120.. | 52515120.. |
1251 | 0.0001757 | 0.0003443 | 85466277.. | 85466277.. |
1301 | 0.0001845 | 0.0003648 | 37789230.. | 37789230.. |
1351 | 0.0001874 | 0.0003891 | 43683143.. | 43683143.. |
1401 | 0.0001988 | 0.0004275 | 12740260.. | 12740260.. |
1451 | 0.0002249 | 0.0004543 | 90700795.. | 90700795.. |
1501 | 0.0002223 | 0.0004541 | 15284515.. | 15284515.. |
1551 | 0.0002331 | 0.0005178 | 59242051.. | 59242051.. |
1601 | 0.0002691 | 0.0005107 | 51413926.. | 51413926.. |
1651 | 0.0002543 | 0.0005915 | 97424275.. | 97424275.. |
1701 | 0.0002705 | 0.0005537 | 39365477.. | 39365477.. |
1751 | 0.0002749 | 0.0005807 | 33170823.. | 33170823.. |
1801 | 0.0002889 | 0.0005958 | 57078464.. | 57078464.. |
1851 | 0.0007958 | 0.0006628 | 19663143.. | 19663143.. |
1901 | 0.0003352 | 0.0006494 | 13309229.. | 13309229.. |
1951 | 0.0003260 | 0.0006742 | 17388238.. | 17388238.. |
...