競プロ2

計算時間

1. 法則
   1. ループ
   2. 計算の規模 magnitute
   3. フェーズ
   4. 変数
   5. 再帰
2. 複雑さのクラス
3. 効率の推定
4. 最大部分配列問題
   1. 最良の値と、max（?番目からk-1番目までの和と、k番目の値）を考える
   2. 後者が前者を超えたら、最良の値を更新する。
   3. Kadane's algorithmと言われる

考え事

基本的な操作（ループ、変数、再帰）

Kadane's algorithm（ループ、変数は2つ best sum、再帰はない）

ちなみに、Kadaneのアルゴリズムは、半環上ならどの演算でも良いらしい（max plus代数、xor and代数とか。集合の演算でもいい。）抽象化することで、アルゴリズムの適用範囲が拡大する。面白すぎる。

詳しくはこちらの記事を参照。

ark4rk.hatenablog.com

変数に対する演算が重要（min, max, sum, product, etc.）

並べ替え

1. 並べ替え理論
   1. バブルソート O(n^2)、左右比べて入れ替え、転換の数
   2. マージソート O(n log(n))、全体を分割して、それをバブルソートする。
      1. 計算量の高い並び替える操作を、上手く分割することで総量を小さくした。
      2. 最悪の事態でも各レベルでは O(n)、それが log(n)個ある
2. 二分探索
   1. どこに目的の要素があるか探す時。
   2. 無情報なら、一つずつ見るより他ない。
   3. しかし、順序が与えられているなら二分探索が有効
   4. 両端から範囲を狭めるパターンと、片側からジャンプの幅を狭めるパターン。
   5. 応用先
      1. その1：単調増加 or 単調減少の数列リストから、目的のものを取ってくる。
      2. その2：上に凸 or 下に凸の数列リストから、最大 or 最小の要素を取ってくる。これは、差分が単調減少 or 単調増加の数列になっている。

考え事

並べ替えは基本的に n log(n)のオーダーで精一杯。

個々の要素から全体の順序を作る操作である並べ替えと、全体の順序をから個々の要素を取り出す操作である二分探索。

秩序の構成と利用の双方からアルゴリズムを考えるべき。