1

フィボナッチ数列と二分探索の再帰関係には慣れていますが、このアルゴリズムの再帰関係を見つける方法がわかりません。

Algorithm strange-sort(A[0,,,,,,n-1])
       if n=2 and A[0]>A[1]
       {
              swap(a[0],a[1])
       }
       else if n>2
       {
              m=ceiling(2n/3)
              strange-sort(A[0.....m-1])
              strange-sort(A[n-m......n-1])
              strange-sort(A[0......m-1]) 
       }

このアルゴリズムの再帰関係を取得するにはどうすればよいですか? それは何を解決しますか？

4

1 に答える 1

4

これがStooge Sortアルゴリズムです。ウィキペディアによると、実行時間は O(n log 3 / log 1.5 ) であり、適切な繰り返しを考え出すことで、その理由がわかります。

各再帰呼び出しは O(1) の作業を行い、サイズ 2n / 3 の 3 つの再帰呼び出しを行うことに注意してください。これにより、再帰関係が得られます。

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

マスター定理を使用してこれを解決できます。ここで、a = 3、b = 3/2、および d = 0 です。log b a = log 1.5 3 > 0 なので、マスター定理により、これは O(n log 1.5 3 ) に解決されます。対数の性質を使用して、これを O(n log 3 / log 1.5 ) に並べ替えます。これは約 O(n 2.70951129135... ) です。

お役に立てれば！

于 2013-11-05T01:06:10.130 に答える