O記法（ビッグオー記法） とは？

データ量nが増えた時に処理時間がどう増えるかを表す。O(1)はnに関係なく一定時間（配列のインデックスアクセス）。O(n)はnに比例（配列の全探索）。O(n²)はnの二乗に比例（二重ループ）。n=1000の時、O(n)は1000回、O(n²)は100万回。O(n²)のアルゴリズムはn=10万で実用不可能になるよ

O記法では無視する。O(2n)もO(100n)もO(n)と書く。nが十分大きければ定数倍より次数の違いが圧倒的に効く。O(n) vs O(n²)はn=1万で1万倍の差になる。ただし実務ではnが小さいケースも多く、定数倍が効くことがある。O(n)でも定数が大きければO(n log n)の方が速いこともあるんだよ

①O(1)：ハッシュテーブルの検索、②O(log n)：二分探索、③O(n)：線形探索、④O(n log n)：ソート（マージソート、クイックソート）、⑤O(n²)：二重ループ、バブルソート、⑥O(2ⁿ)：部分集合の全列挙。面接では「この関数の計算量は？」と聞かれることが多いから、代表的なパターンを覚えておこうね

時間計算量（処理時間）だけでなく、空間計算量（メモリ使用量）もO記法で表す。マージソートは時間O(n log n)だけど空間O(n)が必要。ヒープソートは時間O(n log n)で空間O(1)。メモリが限られる組み込みシステムでは空間計算量が重要。「時間と空間のトレードオフ」はアルゴリズム設計の基本だよ