1

これが私が分析しようとしているアルゴリズムです（以下を参照）。O(n)マージの並べ替えに時間がかかる理由がわかりません O(n logn)。両方とも同じことをしているようです。

次に、両方とも同じ j 時間の複雑さを持ちます。j を行のままにしておくと2^j X c(n/2^j)=cnになり、両方の実行時間はlog nになります。ここで、n は要素の数です。

Algorithm: BinarySum(A, i, n)
Input: An array A and integers i and n.
Output: The sum of the n integers in A starting at index i.
if n = 1 then
return A[i]
return BinarySum(A, i, [n/2] ) + BinarySum(A, i + [n/2], [n/2])

ありがとう、ダニエル

4

3 に答える 3

2

配列の各メンバーを一定時間処理しています。これをどのように行っても、結果の複雑さは O(n) になります。ところで、単純な例としてペンと紙の方法を使用すると、実際には、配列に表示される順序どおりに配列の要素を呼び出していることがわかります。つまり、このアルゴリズムは単純な反復合計と同等です。

O(n) の複雑さの正式な証明は、Master theoremから直接続きます。あなたのアルゴリズムの再帰関係は

T(n) = 2 T(n/2)

これは定理のケース 1 でカバーされます。この複雑さから、次のように計算されます。

O(n ^ log_2_(2)) = O(n)

マージソートに関しては、その再帰関係は

T(n) = 2 T(n/2) + O(n)

これはまったく別の話です - マスター定理のケース 2。

于 2012-08-09T13:40:35.243 に答える
0

アルゴリズムの再帰式は次のとおりです。

 2T(n/2) = O(n)

一方、マージソートの再帰式は次のとおりです。

 2T(n/2) + O(n) = O(n log n)

2 つの再帰呼び出し + O(n) を取るマージ関数の呼び出しがあるためです。関数は 2 つの再帰呼び出しを行うだけです。内訳を確認してください。

http://www.cs.virginia.edu/~luebke/cs332.fall00/lecture3/sld004.htm

于 2012-08-09T13:29:01.447 に答える
0

次の疑似コードを検討してください。

 1    MergeSort(a, p, r)
 2      if  P<r                                // check for base case
 3      then q = FLOOR p+r/2                   // Divide
 4      MergeSort(a, p, q)                     // conquer
 5      MergeSort(a, q+1, r)                   // conquer
 6      Merge(a, p, q, r)                      // Merge

複雑さは次のようになります。

為に

行 3 :- O(1) 一定の時間がかかるため。

4 行目 :- T(n/2) 要素の半分を操作するため。

5 行目 :- T(n/2) 要素の半分を操作するため。

6 行目 :- T(n) すべての要素を操作するため

@Lunar で言及されているように、再帰関係を使用して、時間の複雑さが次のものと同等であると述べることができます:- O(nlgn)

于 2016-06-25T14:14:18.593 に答える