再帰アルゴリズムの複雑さを正しく計算しているかどうかはわかりません。再帰アルゴリズムの複雑さを見つける
あなたはそれを確認し、私が正しいかどうかを教えてください。それはn
が関数に渡された配列内のアイテムの数に等しいn
回反復するため
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)
に等しい複雑性を有します。 2番目の関数は非常に複雑ですが、その複雑さを見つける方法を実際には分かりませんが、それは約O(nlog(n))
となります。 一般的な複雑さはnLog(n) * n = n^2log(n) = n^2
ですか?
私の場合、複雑さを正しく計算する方法を説明してください。
ありがとうございました。ですから、基本的に 'O(log(p)+ log(q))'を無視して全体の複雑さとして 'O(n * log(c))'を取ることができます。 – bxfvgekd
@bxfvgekd 'log(c)'はすべての可能な 'p'と' q'に対する 'log(p)+ log(q)'の漸近的な上限です。 – Gassa