AtCoder 計算量について学ぶ

1週間ぶりに落ち着いた時間ができたので、
久しく放置していた計算量について学びました。

参考：https://qiita.com/drken/items/18b3b3db5735241465ef

AtCoderで使える知識となるよう、メモします。

扱えるループの回数と使用目安

1秒間で扱えるループの回数の目安が、
10**7~10**8(シンプルなら10**9)ということです。

ABC問題の実行時間は２秒程度が多いので、
おおむね上記と同じ10**7~10**9あたりが限界と覚えておきます。

また、上記を踏まえたnの数値は、

n!...n=10程度
2**n...n=20程度
2**n/2...n=30程度
n**4...n=100程度
n**3...n=300程度
n**2...n=10**3~4程度
nlogn...n=10**5~6程度
n...n=10**7~8程度
logn...n=10**9~12程度

色々なアルゴリズムのオーダー

・線形探索...O(n)
・偶数出力...O(n)
・かけ算九九...O(n**2)
・2頂点間最小距離...O(n**2)　→分割統治法によりnlognへ
・行列乗算...O(n**3)
・二進法展開...O(logn)
・ナベアツ...O(logn)
・二分探索...O(logn)
・マージソート...O(nlogn)
・素数判定...O(sqrt(n))
・bit全探索...O(n2**n)
・順列全探索...O(nn!)
・ループ内で素数判定などの重い処理...O(n sqrt(n))
・エラトステネスの篩...O(nlognlogn)

自分の実装しようとしているプログラムがどの程度のオーダーになりそうかを、
前もって意識できるように考えていきたいです。

以上。