这里 n>m。 我分析了最坏的情况，当 n = fibonacci Nth term 和 m = fiboncci (N-1)th term.In this case total work will be proportinal to N or time complexity will O(N).但我有兴趣找到以 n 表示的时间复杂度(theta 表示法)。但我不知道如何找到 n 和 N 之间的关系，或者以 n 表示的上限和下限。
int gcd(int n, int m) {
if (n%m ==0) return m;
if (n < m) swap(n, m);
while (m > 0) {
n = n%m;
swap(n, m);
}
return n;
}
请帮忙。
最佳答案
我会尝试分析两次循环后 m 的变化情况。一次迭代可能对 n 的改变很小，例如 (1001, 1000) -> (1000, 1)。 m 也可能变化很小，例如 (1999, 1000) -> (1000, 999)。因此，分析单次迭代中的任何一种变化对您的帮助都非常小。然而，如果你有两次迭代，那么你总是会有很大的变化。
所以分析一下:如果 r = n/m，在算法两次迭代后 m 如何变化，取决于 r？它至少减少了哪个因素？ (顺便说一句，斐波那契数的 r 是多少？这是否解释了最坏的情况？)
关于algorithm - gcd 算法在大 theta 符号方面的时间复杂度。，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30571718/