5

私は別の SO の質問を解決するアイデアを思いつきました。私はそれについてあまり詳しくないので、関数の複雑さを判断するのに役立つことを望んでいます。各チャンクが「ソート解除」されると推測するのは正しいでしょうか? では、あるチャンクの最後を別のチャンクの先頭と比較する sortBy 関数の複雑さはどのようなものでしょうか? 私の推測では、その関数はペアのみを比較し、合計リストに関して 1 つのチャンクの順序を見つける必要はありません。また、関数全体の遅延最適化のために、Haskell は異なる複雑さを提供しますか? 前もって感謝します！O (n * log 2)

import Data.List.Split (chunksOf)
import Data.List (sortBy)

rearrange :: [Int] -> [Int]
rearrange = concat 
          . sortBy (\a b -> compare (last a) (head b)) 
          . map (sortBy (\a b -> compare b a)) 
          . chunksOf 2
4

2 に答える 2

5

まあ一歩一歩

  1. chunksOf 2リスト全体を反復する必要があるためO(n)、リストの長さの半分になります。ただし、定数の倍数は複雑さに影響しないため、これは無視できます。
  2. map (sortBy...リスト全体O(n)を一定時間操作を繰り返します* O(1)= O(1*n)=O(n)
  3. sortBy一定の時間比較*とはO( n * log n)
  4. concatこれはO(n)

したがって、合計O(n + n + n log n + n)= O ((3 + log n) * n)=O(n log n)

*リストの長さは 2 以下であることが保証されているため、並べ替えや最後の要素へのアクセスなどの操作はそれぞれ一定時間であるO(2 * log 2)と言えます。O(2)O(1)

于 2013-05-26T15:47:13.880 に答える
5

部分を分離して見てみましょう（nリスト引数の長さを見てください）：

  • chunksOf 2O(n)長さのリストになります(n+1) `quot` 2。
  • map (sortBy ...): 渡されるすべてのリストsortBy ...は length<= 2であるため、これらの並べ替えのそれぞれはO(1)であり、したがって全体mapも ですO(n)。
  • sortBy (\a b -> compare (last a) (head b)): 比較は常にです。要素が取得されるO(1)リストの長さは制限されているため ( )、操作全体は次のとおりです。last<= 2sortByO(n*log n)
  • concatO(n)再びです。

したがって、全体として、 がありO(n*log n)ます。

ただし、

cmp = \a b -> compare (last a) (head b)

は一貫性のない比較です。2 つのリストaとb(たとえば[30,10]と[25,15]) の場合、

cmp a b == cmp b a = LT

あなたのアルゴリズムが常に機能するかどうかはわかりません。

の実装を見てsortBy、並べ替えを頭の中で少しトレースした後、指定された目的に対しては機能し (リスト要素が明確である場合)、一貫性のない比較は害を及ぼさないと思います。一部の並べ替えアルゴリズムでは、一貫性のない比較により並べ替えがループする可能性がありますが、マージ並べ替えバリアントでは発生しないはずです。

于 2013-05-26T15:47:42.707 に答える