再帰アルゴリズムの複雑さを見つける

Question

再帰アルゴリズムの複雑さを正しく計算しているかどうかはわかりません。

あなたはそれを確認し、私が正しいかどうかを教えてください。それは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 ですか？

私の場合、複雑さを正しく計算する方法を説明してください。

Answer 1

内部関数はbinary GCDであり、その複雑さはO(log(p) + log(q))です。 あなたが詳細については、リンクをたどることができますが、基本的には、引数の少なくとも一方がO(1)ステップで半分になるので、これ以上log(p) + log(q)以下の手順は、外側のループの実行1.

にpとqダウンの両方をもたらすために必要とされていますn回ですので、基本的に上限はO(n * log(c))です。cは、input配列の可能な最大要素です。

nの数字2 ^kのコピーで構成される入力の場合、基本操作の数は実際にはn * kです。 kはlog(c)に比例することに注意してください。 したがって、境界は正確です。

---

第二の機能は非常に複雑で、私は本当に、その複雑さを発見する方法を見つけ出すことはできませんが、私はそれがO（nlog（n））を約あると仮定し、上記ご了承のためとして

私はnが入力の長さであると仮定します。最初は内部関数にはnがありません。 両方の引数はただlong秒であり、入力の数に依存しません。

---

そして、サイドノートとして、私たちは、内部関数としてスタインのGCDの代わりにEuclid's GCDを使用した場合、私は、全体の複雑さがちょうどO(n + log(c))までO(n * log(c))から行くだろうと信じています。