Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

Лабораторная работа по «Алгоритму и структуре данных»

Автор:   •  Май 14, 2023  •  Лабораторная работа  •  791 Слов (4 Страниц)  •  138 Просмотры

Страница 1 из 4

Ульяновский государственный технический университет

Факультет информационных систем и технологий

Кафедра «Измерительно-вычислительные комплексы»

Дисциплина «Алгоритмы и структуры данных»

Лабораторная работа №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..

...

Скачать:   txt (6.2 Kb)   pdf (145.6 Kb)   docx (83.4 Kb)  
Продолжить читать еще 3 страниц(ы) »
Доступно только на Essays.club