Big O時間の複雑さとは？

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

Big O表記法は、入力サイズが大きくなると演算量がどんな速度で増加するかを表現する。 正確に何ナノ秒かかるかを言うベンチマークとは目的が違う。

よく見る複雑さ

O(1) 配列インデックスへのアクセス
O（log N）バイナリナビゲーション
O(N) 全体巡回
O（N log N）一般的な比較ソート
O(N²) すべてのペアの比較

定数は省略する

for (int Value : Values)
{
    ProcessA(Value);
}

for (int Value : Values)
{
    ProcessB(Value);
}

二度巡回するので、実際の演算は2Nに近いがビッグオではO(N)で表現する。 Ｎが大きくなると増加する次数に集中するからだ。

定数を無視しても実際の性能では定数が重要ではないわけではない。 キャッシュフレンドリーO(N)コードが複雑な定数を持つ他のO(N)コードよりはるかに高速です。

最悪、平均、ベスト

線形ナビゲーションは、最初の要素で見つけるとO(1)だが、いないか最後にあればO(N)である。 どんな場合を言うか少なくなければ、同じアルゴリズムを互いに異なって説明することになる。

Big Oはアルゴリズムを選ぶ最初のフィルタです。 最終的な選択は、実際のデータサイズ、メモリ使用量、キャッシュ、実装の複雑さとともに判断する必要があります。