文字列ソートの実行時間(Big-O記法)
(700ページ超えの大著、誤植多し..
例題
文字列の配列Aがあり、配列Aに格納された各文字列をソートした上で、
配列A全体をソートする場合の計算量はBigO記法でどうなるか？
直感的に考えた答え
各文字列の長さがsとすると、各文字列のソート 計算量はO(s log s)
それをさらに配列長aに大して行うので、配列全体のソートがO(a log a)
とすると、
O(s log s + a log a)？
↓
これは誤り.
(せめて各文字列に対するソートを、配列の要素数だけ計算するので、
その考えだと前者はO(a*s log s)となる。
これであれば、前者については正しい。
解答
配列A内の全要素に対する各文字列ソート の計算量はO(a*s log s)
配列A全体のソートを考えると
文字列と文字列との比較自体にはO(s)かかる
配列全体のソート回数はO(a log a)
配列長はaだから。
よって、文字列比較O(s)をソート回数O(a log a)行うため、O(a*s log a)となる
本書ではO(a*s log s)と書かれてるが、これは誤植??
したがって、全体計算量は O(a*s(log a + log s))となる、とのこと。
ポイント
上記のsとaを混同してNとし、O(N^2 log N)等とするのも、ありがちなミスらしい