Open2021/05/13にコメント追加6

競プロのための標準 C++ | 編集ノート

計算量表記の追加に関する話

もう少し細かく記載する？
- 例: std::partial_sort(first, middle, last): およそ $(last-first)log(middle-first)$

個人的には両方載せるのもありかと思いましたがちょっと長いですかね？
厳密な方は脚注にというのもあるかもしれません

std::partial_sort(first, middle, last): $O(N\log{N})$
厳密には $(last-first)\log{(middle-first)}$

対象読者層を詳しくはわかってないんですけど考えてたことはこんな感じです

計算量とオーダーの記法についての簡単な説明
- (O記法,θ記法,Ω記法と慣例)
各項目の計算量
- std::min(a,b) みたいな明らかにO(1)に見える関数にも計算量を一応載せるかどうか
- 仕組みや証明を簡単に(unorderedsetの関数,std::gcdなど) (要らないかもしれません)

計算量とオーダーの記法についての簡単な説明

1 ページにコンパクトにまとめて用意したいですね。誰か書いてくれるかな。長くなる場合や、発展的な資料がある場合は参考リンクとして貼る、という感じでもよいです。

std::min(a,b) みたいな明らかにO(1)に見える関数にも計算量を一応載せるかどうか

cppreference には各関数に Complexity の説明があって、
https://en.cppreference.com/w/cpp/algorithm/min だと「ちょうど 1 回の比較」のように書かれています。

仕組みや証明を簡単に(unorderedsetの関数,std::gcdなど) (要らないかもしれません)

この本では、標準機能の「使い方」に重きを置いているので、優先度は低いです。