Hatena::Grouphaskell

Haskellで遊ぶよ

 | 

2009-06-25

unwordsはO(n^2)?

14:34

unwords          :: [String] -> String
unwords []       =  ""
unwords ws       =  foldr1 (\w s -> w ++ ' ':s) ws

w は継ぎ足す度にどんどん大きくなっていく。単語の長さの平均を a とすると、w の大きさは最初が a、次が 2*a、次が 3*a、となる。全体のステップ数は

a + 2*a + 3*a + ... + n*a = a*n*(n+1)/2

で O(n^2) だと思うんだけど、print に繋げる場合などは、出来た部分から順に出力していけばいいのだから (実際そうなってる) 最適化されるのだろうか?

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20090625
 |