計算量の目安
- 10の7乗くらいはたいがい間に合う
- 10の8乗はシンプルな処理なら間に合う
- 10の9乗はめちゃくちゃシンプルなら間に合う
各オーダーに対してぎりぎり間に合うNの値
$10^8$ くらいを目安にして、キリのいい値を求める。
| オーダー |
間に合う N の値 |
| $O(N)$ |
$10^8$ |
| $O(N^2)$ |
$10^4$ |
| $O(N^3)$ |
$500$ |
| $O(N^4)$ |
$100$ |
| $O(N^5)$ |
$40$ |
| $O(N^6)$ |
$20$ |
| $O(2^N)$ |
$26$ |
| $O(N\cdot 2^N)$ |
$22$ |
| $O(N^2\cdot 2^N)$ |
$19$ |
| $O(3^N)$ |
$16$ |
| $O(N!)$ |
$11$ |
オーダー改善テク
定数倍改善テク
- ボトルネックの部分のみ最適化をする
- ボトルネックじゃないところはどうでもいい
- ボトルネックの部分はかなり狭い場合もある
- HashMap の代わりに Vec を使う
- ループの外でできる処理はループの外でする
- 最初は普通に実装する。最初から最適化はしようとしない。
- 添字アクセスは遅いので iterator を使う
- どうしても添字アクセスが必要な場合は
get_unchecked や get_unchecked_mut を使う
- 配列の動的確保は遅いのでできるだけ避ける
- 出力には fastout を使う
- &u32 より u32 を使う
- iter().copied() の copied() をすると早くなることがある