if 和 while 循环的时间复杂度 m!=n

Question

while (m != n) {
  if (m > n)
    m = m - n;
  else
    n = n - m;
}

如果(m>n)，时间复杂度应为(m/n)-1；如果(n>m)，时间复杂度应为(n/m)-1。请告诉我它的O(n)是怎样的。 如果我取 m=32 且 n=8： 那么它应该在 4 (=32/8) 左右的迭代内完成。但其时间复杂度为O(n)。 我尝试分析问题但无法分析它

Answer 1

OP中的代码实现了欧几里得算法的原始版本。

最坏情况的复杂度在两个参数中都是线性的。要看到这一点，请考虑

m

为 1 和

n

某个任意正整数。在这种情况下，必须执行

n-1

迭代，从

n

中减去 1，直到

n

也变为 1。因此，在这种情况下，复杂度为

O(n)

。当

n=1

和

m

任意给出复杂性

O(m)

时，存在对称情况。

具有任意正数

n

和

m

，迭代次数在所有情况下都小于

n+m

。

因此，最坏情况的复杂度是

O(n+m)

，如果假设是

n>m

，那么这就是

O(n)

。

为了完整起见，应该提到的是，当用除法实现时，欧几里得算法的复杂度是

O(log(min(n,m)))

。