Big Oは、定数倍を無視して、入力が大きくなるにつれて処理がどう増えるかを表します:
- O(1):辞書や集合の参照のように、どんな大きさでも同じ処理量です。
- O(n):データを1回走査します。
- O(n log n):並べ替えです。
- O(n²):同じデータに対するループの中のループです。行が10倍になると、処理は100倍になります。
1行の中に隠れたループもあります。x in a_listはリストを調べるので、別のリストのすべての項目についてそれを行うとO(n²)です。x in a_setは平均でO(1)なので、集合を一度だけ作れば、作業全体がO(n)になります。ループの中のlist.index、list.count、list.removeも同じです。
もう1つの工夫は、一度計算して再利用することです:累計を使えば、「iからjまでの合計」の質問のどれにも1回の引き算で答えられます。
このユニットでは、隠された確認で数千個の項目を持つ入力を使います。2乗の答えは、小さなデータで正しくても時間切れになります。