关于辗转相减法循环时间复杂度为何为O(n)的技术咨询

先看你给出的代码：

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

首先纠正你举的例子：当m=32、n=8时，实际迭代次数是3次（32→24→16→8，总共3次减法操作），确实等于(32/8)-1，这个计算没问题，但这只是两个数成整数倍时的最优情况，时间复杂度分析得看最坏场景。

为什么资料说时间复杂度是O(n)？看这种极端情况：比如m=100，n=99。这时候循环要跑99次：

• 第一次：m变成100-99=1
• 接下来的98次：n每次减1，从99降到98，再到97……直到n=1，此时m=n，循环结束

这种情况下，循环次数等于较小数的数值，也就是O(n)（假设n是两个数里更小的那个）。

再比如两个数是斐波那契数列的连续项，比如m=8、n=5，m=13、n=8这类，每次相减只能让大数缩小成小数减前一项，迭代次数会跟着数列长度线性增长，最终也趋近于O(n)的复杂度。

你的分析只覆盖了倍数关系的场景，这是迭代次数最少的情况，但时间复杂度标注的是最坏情况下的性能上限，所以资料给出的O(n)是准确的。

内容的提问来源于stack exchange，提问作者Sampada Gupta