まず
未来の人たちのためのシリーズなので、これでわからなかったら、AIやPAIZAなどを閲覧することを強くすすめします。
オーダー表記とは
厳密には違うけど簡単にいえば、どんくらいパソコンが計算するかというもので、O（処理回数）と書きます。例えば、O（100）だったらパソコンが100回計算する。
変数の場合
例えば、
のとき
① 1番大きい次数以外を消す → 3nの2乗になる
②係数を消す →nの2乗になる
よってO（nの2乗）のなる
競プロでの使い方
めっちゃ重要なんだけど、計算量が10億（10の9乗）になったら基本TLE（タイムエラー）になってパソコンが爆発します。（ほんとには爆発しない）
なので、どうにかして計算量を減らす
よく見る削減
どのようにやるかは、その問題次第だけど大体決まってて、
- O（nの2乗） → O（n）、O（n＊logn) これが何気に1番多い
- O（n） → O（logn) 二分探索でやる
- O（n＊m） → （n +m） 累積和でやる
耐えられる計算量
O（nの2乗） n が3万ぐらいまで耐える
O（2のn乗） nが30まで耐える
O（n＊logn) nが多分4000万まで耐える
O（logn) nが10の3億乗まで耐えるらしい
最後に
わからなくてもO（）は計算回数って思ってください
コメント