2010-02-22 ディスカッション 来客がありディスカッション.とりあえず問題を聞いて,O(n log n) のアルゴリズムを見せてもらい,それがO(n)にできるか,あるいはΩ(n log n)の下界があるか考える.家に帰ってきてから少し考えたら,O(n)ができそうな気がしてきた.また明日.