Алгоритм Эвклида

@FloraWinx · Регистрация: 05.10.2013

Author24 — интернет-сервис помощи студентам

Как оценить сложность алгоритма Эвклида для поиска наибольшего общего делителя?

@Mysterious Light · 23.10.2013, 23:41

Гугл нам даёт следующие две ссылки на первой странице:
http://mitrof3.narod.ru/crypto... .3.3.3.rtf
http://it.kgsu.ru/TI_7/salg_009.html

Читая, можно следующее выделить:

Оценим сверху количество рекурсивных вызовов функции GCD. Для этого выпишем последовательно соотношения, определяющие аргумент X. Предположим для определенности, что n > m (при обратном неравенстве первый вызов функции просто меняет аргументы местами, а при равенстве n = m процесс завершается за один шаг). В качестве параметра V сложности исходных данных целесообразно принять меньший из аргументов функции, т.е. V = m, так как именно с него начинаются операции деления (нахождения модулей) - если увеличить m на произвольно большое число, кратное m (например, m*10¹⁰⁰⁰), то это не изменит количества шагов. Следовательно, max(n,m) не является хорошим аргументом функции сложности.

Вывод средней оценки сложности алгоритма Евклида приведен в книге Д. Кнута (Т. 2, разд. 4.5.3). Однако, когда оценка худшего случая всего лишь логарифмическая, средняя оценка представляет, в основном, теоретический интерес (в данном случае она тоже логарифмическая, но с меньшим коэффициентом).

Оценка сводится к ряду Фибоначчи, её ассимптотика также приводится.

@FloraWinx 4 / 4 / 0 Регистрация: 05.10.2013 Сообщений: 123
		1
	Алгоритм Эвклида 23.10.2013, 19:45. Показов 3982. Ответов 1 Метки алгоритм эвклида, сложность алгоритма (Все метки) Как оценить сложность алгоритма Эвклида для поиска наибольшего общего делителя? 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,162 Записей в блоге: 24
	23.10.2013, 23:41	2
	Гугл нам даёт следующие две ссылки на первой странице: http://mitrof3.narod.ru/crypto... .3.3.3.rtf http://it.kgsu.ru/TI_7/salg_009.html Читая, можно следующее выделить: Оценим сверху количество рекурсивных вызовов функции GCD. Для этого выпишем последовательно соотношения, определяющие аргумент X. Предположим для определенности, что n > m (при обратном неравенстве первый вызов функции просто меняет аргументы местами, а при равенстве n = m процесс завершается за один шаг). В качестве параметра V сложности исходных данных целесообразно принять меньший из аргументов функции, т.е. V = m, так как именно с него начинаются операции деления (нахождения модулей) - если увеличить m на произвольно большое число, кратное m (например, m*10¹⁰⁰⁰), то это не изменит количества шагов. Следовательно, max(n,m) не является хорошим аргументом функции сложности. Вывод средней оценки сложности алгоритма Евклида приведен в книге Д. Кнута (Т. 2, разд. 4.5.3). Однако, когда оценка худшего случая всего лишь логарифмическая, средняя оценка представляет, в основном, теоретический интерес (в данном случае она тоже логарифмическая, но с меньшим коэффициентом). Оценка сводится к ряду Фибоначчи, её ассимптотика также приводится. 0