time-complexity - gcd 的时间复杂度是 Θ(logn) 吗？

Question

我正在解决Interview Bit上的一个时间复杂度问题，如下图所示。

给出的答案是Θ(theta)(logn)我无法理解 logn 项是如何在这个程序的时间复杂度中到达这里的。
有人可以解释一下 logn 的答案是什么吗？

Answer 1

定理 给定任何 x, gcd(n, m) 其中 n < fib(x) 被递归称为等于或小于 x 次。

注意:fib(x) 是 fibonacci(x)，其中 fib(x) = fib(x-1) + fib(x-2)

证明

基础

每 n <= fib(1), gcd(n, m) 是 gcd(1,m) 只递归一次

感应步

假设定理对于每个小于 x 的数都成立，这意味着:

calls(gcd(n, m)) <= x for every n <= fib(x)

考虑 n 其中 n <= fib(x+1)

如果 m > fib(x)

   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

如果 m <= fib(x)

   calls(gcd(n, m))
=  calls(gcd(m, (n%m))) + 1  because m <= fib(x)
<= x + 1

所以该定理对 x + 1 也成立，作为数学归纳法，该定理对每一个 x 都成立。

结论

gcd(n,m) 是 Θ(reverse fib) 也就是 Θ(logn)