5

この問題が発生しました「このメソッドを実装して、特定の配列内の最大 2 つの数値の合計を返します。」

私はこの方法でそれを解決しました：

 public static int sumOfTwoLargestElements(int[] a) {

     int firstLargest = largest(a, 0, a.length-1);

     int firstLarge =  a[firstLargest];
     a[firstLargest] = -1;

     int secondLargest = largest(a, 0, a.length-1);

     return firstLarge + a[secondLargest];
}

private static int largest(int s[], int start , int end){

    if (end - start == 0){

        return end;
    }


   int a = largest(s, start, start + (end-start)/2) ;
   int b = largest(s, start + (end-start)/2+1 , end);
    if(s[a] > s[b]) {

       return a;
    }else {

      return b;
    }

}

説明: メソッド「largeset」を実装しました。このメソッドは、指定された配列内の最大数を取得する責任があります。

同じ配列でメソッドを 2 回呼び出します。最初の呼び出しで最初に最大の数値が取得されます。それを変数に入れ、配列の「-1」数値に置き換えます。次に、最大のメソッドを 2 回呼び出します。

このアルゴリズムの複雑さを教えてくれる人がいますか? お願いします

4

3 に答える 3

11

アルゴリズムの時間計算量は ですO(n)。

各再帰呼び出しの複雑さは、実際には次のとおりです。

f(n) = 2*f(n/2) + CONST

(帰納法1により) f(n) <= CONST'*n- であることは簡単にわかりO(n)ます。

スペースの複雑さはO(logN)、これが再帰の最大の深さであるためO(logN)、呼び出しスタックにメモリを割り当てることです。

(1) 使用するf(n) = 2*n*CONST - CONSTと、次のようになります。

f(n) = 2*f(n/2) + CONST = (h.i.) 2*(2*CONST*n/2 - CONST) + CONST =
=  2*n*CONST - 2CONST + CONST = 2*n*CONST - CONST

(ベースの確認は読者の課題として残しています)

于 2013-07-12T18:37:02.600 に答える