#リストのリストを要素であるリストの長さでソートする．
sortByLength,sortByLength' :: [[a]] -> [[a]]
sortByLength = sortBy (comparing length)
sortByLength' = map fst . sortBy (comparing snd) . map ((,) <*> length)
リストのリストの長さを n，要素のリストの長さをm とすると
sortByLength は O(m n log n) ？
sortByLength'は O(max (mn , n log n)) ってこんな書きかたできるのかな．
#O(f(x)) は x がどんどん大きくなる時のふるまいだから、どんどん大きくなるのが何かによって変わってきますね。
#で、sortByLengthでO(m n log n)と書く場合はm, nがともにどんどん大きくなると考えてるってことですよね (nだけ大きくするなら n log nでいいんで)
#そうなると、
#sortByLength' だと mn 項も n log n項も無視できなさそうな?
#mとnの「大きくなり方」の違いが重要になるのかな。
#m/n が 定数×log n で抑えられるかどうか、で分岐する
haskell-ja > Archives > 2009/05/18