Сложность времени следующей функции

Question

В следующей функции C++ пусть n> = m.

int gcd(int n, int m) { 
      if (n%m ==0) return m; 
      if (n < m) swap(n, m); 
      while (m > 0) { 
       n = n%m; 
       swap(n, m); 
      } 
      return n; 
    } 

Какова временная сложность вышеуказанной функции, предполагающей n> m? Ответ на этот вопрос - O (log n), но я не понимаю, как он рассчитан?

Answer 1

на каждой итерации значение n уменьшается в среднем по коэффициенту золотого отношения. Я предлагаю попробовать отработать в худшем случае, и это должно быть около логарифм 1.618 n

Для получения более подробной информации https://en.wikipedia.org/wiki/Euclidean_algorithm, который отмечает: «Если алгоритм Евклида требует N шагов для пары натуральных чисел а> Ь> 0, то наименьшие значения a и b, для которых это верно, - числа Фибоначчи F (N + 2) и F (N + 1) соответственно.

например. Если вы начинаете с Fib (n + 2) и Fib (n + 1), вы получите Fib (n) и Fib (n + 1) на следующей итерации до тех пор, пока не остановитесь на 1.

Answer 2

Сначала рассмотрите эти две возможности для while цикла:

1. в петле, приведенной ниже, сложность этого цикла является O(n) , потому что алгоритм растет пропорционально его вход н:

   while (n > 0) { 
       n = n-1; 
       ... 
   } 
   

2. в то время как в петле, приведенной ниже , так как существует вложенный цикл, th e время будет O(n^2).

   while(n>0) { 
       n = n-1; 
       while(m>0) { 
        m = m-1; 
        ... 
       } 
   } 
   

3. Однако в алгоритме, который вы при условии, вы не прохождения цикла для каждого m или n; вместо этого вы просто используете , используя подход «разделяй и властвуй», и вы просматриваете только часть всего n в вашей петле. На каждой итерации значение n не снижается лишь на фактор 1, но в большем соотношении:

   while (m > 0) { 
       n = n%m; 
       swap(n, m); 
   }