Я решал вопрос сложности во время битва интервью, как показано на рисунке ниже. 
Как временная сложность gcd равна Θ (logn)?
Ответ дан Θ(theta)(logn), и я не могу понять, как прибывает сюда термин logn во временной сложности этой программы.
Может кто-нибудь объяснить, как ответ тета logn?
Этот алгоритм генерирует уменьшающуюся последовательность целых чисел (m, n) пар. Мы можем попытаться доказать, что такая последовательность распадается достаточно быстро.
Предположим, мы начинаем с m_1 и n_1, с m_1 < n_1.
На каждом шаге мы принимаем n_1 % m_1, который < m_1, и повторить рекурсивно по паре m_2 = n_1 % m_1 и n_2 = m_1.
Теперь, скажем n_1 % m_1 = m_1 - p для некоторых p, где 0 < p < m_1. У нас есть max(m_2, n_2) = m_1 - p.
Давайте сделаем еще один шаг (m_2, n_2) -> (m_3, n_3), мы можем легко увидеть, что max(m_3, n_3) < p, но это также верно, что max(m_3, n_3) < m_1 - p, поскольку последовательность строго уменьшается.
Таким образом, мы можем написать max(m_3, n_3) < min(m_1 - p, p), где min(m_1 - p, p) = m_1/2. Этот результат выражает тот факт, что последовательность уменьшается геометрически, поэтому алгоритм должен заканчивать не более log_2(m_1) шагов.
Теорема для любых x, gcd (n, m), где n < fib (x) рекурсивно называется равным или меньше x раз.
Примечание: FIB (х) Фибоначчи (х), где FIB (х) = FIB (х-1) + FIB (х-2)
доказательства
Основа
< каждого п = FIB (1), НОД (п, м) НОД (1, м) только один раз рекурсивным
Индуктивный шаг
Предположим теорема выполняются для каждого числа меньше, чем х, что означает:
calls(gcd(n, m)) <= x for every n <= fib(x)
рассмотрим п где п < = FIB (х + 1)
если т> Фибо (х)
calls(gcd(n, m))
= calls(gcd(m, (n-m))) + 1
= calls(gcd(n-m, m%(n-m))) + 2 because n - m <= fib(x-1)
<= x - 1 + 2
= x + 1
< если т = FIB (х)
calls(gcd(n, m))
= calls(gcd(m, (n%m))) + 1 because m <= fib(x)
<= x + 1
Итак, теорема справедлива и для x + 1, как математическая индукция, теорема верна для любого x.
Заключение
НОД (п, т) является Θ (обратный FIB), который является Θ (LOGN)