查找递归算法复杂性

Question

我不确定我是否正确计算了递归算法的复杂性。

你能检查一下，看看我是否正确。

public static long gcdMultiple(long[] input) {
long result = input[0];
for (int i = 1; i < input.length; i++) result = gcd(result, input[i]);
return result;
}
public static final long gcd(long q, long p) {
if (q == 0) return p;
if (p == 0) return q;
// p and q even
if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;
// p is even, q is odd
else if ((p & 1) == 0) return gcd(p >> 1, q);
// p is odd, q is even
else if ((q & 1) == 0) return gcd(p, q >> 1);
// p and q odd, p >= q
else if (p >= q) return gcd((p - q) >> 1, q);
// p and q odd, p < q
else return gcd(p, (q - p) >> 1);
}

第一个函数gcdMultiple的复杂度等于O(n)，因为它迭代n次，其中n等于传递给函数的数组中的项数。 第二个函数要复杂得多，我真的不知道如何找到它的复杂性，但我认为它是关于O(nlog(n))所以常见的复杂性是nLog(n) * n = n^2log(n) = n^2我说的对吗？

请解释如何在我的情况下正确计算复杂性。

Answer 1

内部函数是二进制GCD，其复杂性O(log(p) + log(q))。 您可以点击链接了解详细信息，但基本上，至少有一个参数在O(1)步中减半，因此只需log(p) + log(q)个步骤即可将p和q降低到 1。

外部循环运行n次，因此基本上，我们有上限O(n * log(c))其中c是input数组中最大可能的元素。

对于由数字 2^k的n个副本组成的输入，基本操作的次数确实是n * k。 请注意，k与log(c)成正比。 所以界限是准确的。

---

第二个函数要复杂得多，我真的不知道如何找到它的复杂性，但我认为它是关于 O(nlog(n))

至于你上面的注释，我假设n输入的长度：首先内部函数没有n。 这两个参数都只是longs，不依赖于输入的数量。

作为

---

旁注，如果我们使用欧几里得的GCD代替斯坦的GCD作为内部函数，我相信整体复杂性将从O(n * log(c))下降到O(n + log(c))。