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

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

https://ru.wikipedia.org/wiki/Алгоритм_Евклида
Тут формулы есть
Максимум О(n*m)

А что такое О

Время работы алгоритма оценивается теоремой Ламе, которая устанавливает удивительную связь алгоритма Евклида и последовательности Фибоначчи:

Если a > b >= 1 и b < F(n) для некоторого n, то алгоритм Евклида выполнит не более n-2 рекурсивных вызовов

(3) читается как "О большое",.... https://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое

Тот факт, что число шагов, затрачиваемых алгоритмом Евклида, растет логарифмически, связан с числами Фибоначчи:

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

(5) спс

(3) фшколу!

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

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

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

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

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

(13) Может, в метро?

(14) Как смешно