計算量オーダーが気になったので調べてみました

家にある本をパラパラめくっていたら、
「計算量オーダー」なる単語が目に入りました。

何でも、ｎを使った計算の量を表した式、
例えば(n+1)n/2とか、2(n-1)とかが、
nに対して何次式なのかを表したものだそうです～

表記はO(N²)とかO(N)といった感じで書きます～

では、どんなものがあるのでしょうか～

O(Kⁿ)…指数オーダー。Nが１０以上ならほぼ計算不可だそうです～

O(N³)…工夫してない連立1次方程式はこの次数になるそうです～

O(N²)…よく見る次数。工夫しないソートなどがこれになるそうです～

O(N)…forループがこれ。N個のものから探すも工夫しないとこれです～

O(logN)…二分検索がこの次数～

O(1)…一発で終了する処理はこれになります～

設計の仕方によっては、次数を減らせられます～
例えば、ただのソートをクイックソートにする、(O(N²)→O(N logN))
N個のものから探すのを二部検索にするとか～ (O(N)→O(logN))

重いなぁと感じた時、今何次式かな？
と意識するのは設計や実装するうえで大事かもしれません～