Как рассчитать математически сложность времени этого алгоритма?

Question

Я пытаюсь понять временную скопленность алгоритма, и у меня есть некоторые проблемы с этим. Может кто-нибудь объяснить мне, как я могу математически рассчитать сложность этого алгоритма?

ALG(m,n)

1. if m > n then
2.   return ALG(m - n, n)
3. else if n > m then
4.   return ALG(n, m)
5. else
6.   return n

Answer 1

Это рекурсивная функция.Когда m> n , он вызывает эту функцию снова с параметром (mn, n) .Поэтому в худшем случае предположим, что когда m = 100 , n = 1 , тогда значение параметра на каждом шаге равно -

 1. m = 100, n = 1
 2. m = 99, n = 1  // because new m will be (m-n), and n remains same according to step 2 in your algorithm
 3. m = 98, n = 1  // same as previous comment
 4. m = 97, n = 1
  .........
  .........
  .........
 99. m = 2, n = 1
 100. m = 1, n = 1
 And then it executes steps 7 in your algorithm.

Итак, в целом ваш алгоритм 100 умноженное на максимальное значение между m и n.

А когда m

Таким образом, сложность этого алгоритма составляет O (max (m, n)) .

Answer 2

Помимо того, что предоставил Фарук Хоссейн.

Верхняя граница может быть уменьшена дополнительно до

O(n,m) = a/b + b/gcd(a,b) 
  where a = max(n,m) and b = min(n,m) 

при соблюдении этого алгоритма вычисляет gcd. a / b - количество шагов, необходимых для второй секунды, если оператор «пинает», и после этого самое большее b/gcd(n,m) дополнительные шаги требуются один раз