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

a = 100 で、b が 100 未満の任意の値であるとします。最悪の場合、a % b の最大値は何ですか? その 49 は、b = 51 の場合のみです。これは、最悪の場合でも、反復ごとに a の値が半分になることを意味します。

これが O(LOGN) アルゴリズムです。

Answer 2

グーグルを試してみてください。GCD にユークリッド アルゴリズムを使用しています。これは、このためのアルゴリズム効率に関するウィキペディアの記事です。