時間計算量 とは？

データがn個の時、処理回数がnに比例するという意味。配列の全要素を1回ずつ見る処理がO(n)。nが2倍になれば処理時間も2倍。O(n²)はデータが2倍になると処理時間が4倍、O(2^n)は1つ増えるだけで2倍になる。定数倍は無視して成長の「傾向」を表すのがO記法のポイントだよ

データ量1万件でO(n²)だと1億回の処理。O(n log n)なら約14万回。差は約700倍。100万件ならO(n²)は1兆回で実質不可能、O(n log n)なら2000万回で余裕。だから大量データを扱う場面ではO(n²)のアルゴリズムを避けるのが鉄則。「とりあえず動くコード」と「スケールするコード」の違いはここにあるよ

理論的にはYes、実務的にはNoだね。O(n)でも定数倍が大きければO(n log n)より遅いことがある。特に小さいnでは定数倍やオーバーヘッドが支配的。キャッシュのヒット率やメモリアクセスパターンも実際の速度に影響する。でもnが大きくなれば成長率が支配するから、まずはO記法で考えるのが正しいアプローチだよ

①ハッシュテーブルの検索=O(1)、②ソート済み配列の二分探索=O(log n)、③配列の線形探索=O(n)、④効率的ソート=O(n log n)、⑤二重ループ=O(n²)。この5つを覚えておけば「この処理は遅くなりそう」という勘が働くようになる。あとは「O(n²)以上はnが1万を超えると厳しい」という体感値を持っておくと実務で役立つよ