Алгоритм Евклида. Как вычислить число итераций? #750817

Добрый день. Подскажите, пожалуйста, решение вот такой задачи. Даны два числа, m и n. Надой найти их наибольший общий делитель. Ищется он по алгоритму Евклида: 1. Делим m на n, получаем остаток r. 2. Если r=0 то n - искомое значение и мы прекращаем алгоритм. 3. Присваиваем m=n, n=r. 4. Переход к шагу 1. Нужно определить среднее число итераций, если известно m и n. Подскажите, пожалуйста, решение с доказательствами?

Что такое среднее число итераций

Тут формулы есть Максимум О(n*m)

А что такое О

Время работы алгоритма оценивается теоремой Ламе, которая устанавливает удивительную связь алгоритма Евклида и последовательности Фибоначчи: Если a > b >= 1 и b < F(n) для некоторого n, то алгоритм Евклида выполнит не более n-2 рекурсивных вызовов

читается как "О большое",....

Тот факт, что число шагов, затрачиваемых алгоритмом Евклида, растет логарифмически, связан с числами Фибоначчи: Теорема (Ламэ, 1845 г.).  Пусть  n   О   N   , и пусть  a  >  b  > 0 такие, что алгоритму Евклида для обработки  а  и  b  необходимо выполнить точно  n  шагов (делений с остатком), причем  а  - наименьшее с таким свойством. Тогда  а  =  F   n   +2  ,  b  =  F   n   +1  , где  F   k   -  k-  ое число Фибоначчи. Доказательство можно посмотреть, например, здесь: С помощью этой теоремы можно оценить порядок роста алгоритма Евклида. Пусть a будет меньшим из двух аргументов процедуры. Если процесс завершается за k шагов, тогда должно выполняться a>=Fib(k), т.е. приблизительно равно f^5/sqrt - золотое сечение. Следовательно, число шагов k растет как логарифм a(по основанию f)!

спс

фшколу!

не уверен, мне первый раз про О и о разъяснили на матане в универе.

Хорошо. Фвысшуюшколу.

тогда уж в высшую техническую школу... на филфаках матанов не преподают.

Ты отстал от жизни. Лет на 80. Но в матане сложность алгоритмов точно не дают

я где-то проходил сложность алгоритмов, но где не помню из башки выветрилось

Может, в метро?

Как смешно