time-complexity - LCM的复杂性

Question

找到 LCM 的代码复杂度是多少。这种复杂性永远不会是 O(n)。此外，步骤会根据输入而有所不同。谢谢。

public static int findGCD (int a, int b) {
    int c;
    do {
        c = a % b;
        if (c > 0) {
            a = b;
            b = c;
        }
    } while (c != 0);
    return b;
}

Answer 1

试试谷歌。您正在为 GCD 使用欧几里得算法。这是有关此算法效率的维基百科文章。

Answer 2

假设 a = 100 且 b 是任何小于 100 的值。在最坏的情况下，a % b 的最大值是多少？只有当 b = 51 时才为 49。这意味着即使在最坏的情况下，每次迭代时 a 的值都会减半！

所以这是 O(LOGN) 算法。