gcd的时间复杂度如何是Θ(logn)？

Question

我在Interview Bit上解决了时间复杂度问题,如下图所示.

给出的答案是?(theta)(logn),我无法掌握登录术语如何到达此计划的时间复杂性.

有人可以解释一下logn的答案是什么？

Answer 1

该算法生成整数对的递减序列(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), where min(m_1 - p, p) = m_1 / 2。这个结果说明了序列呈几何递减的事实，因此算法最多只能终止log_2(m_1)。