求一个递归算法的复杂度

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

内函数为binary GCD，复杂度为O(log(p) + log(q))。您可以按照 link 了解详细信息，但基本上，至少有一个参数在 O(1) 步中减半，因此只需 log(p) + log(q) 步就可以将两个 p 和 q 下降到 1.

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

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

Second function is much complex, I really cannot figure out how to find its complexity, but I assume it is about O(nlog(n))

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

附带说明一下，如果我们使用 Euclid's GCD 代替 Stein 的 GCD 作为内部函数，我相信整体复杂度将从 O(n * log(c)) 下降到 O(n + log(c)) .

求一个递归算法的复杂度

Find a recursive algorithm complexity

algorithm

recursion

performance

complexity-theory