計算量オーダーについて

経緯:

面接でコーディングテストあると、だいたい聞かれる。ので、勉強しておいたほうがいい。

参考サイト:

計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita

線形探索法

一つずつ辿る方法。

例えば、1から10までのデータがあった場合に、そこから数をあてる処理を考えます。

線形探索法では1から10まで 1つずつ試していく 処理を行います。

オーダー: O(n)

二分探索法

半分に分けて不要な処理を省いていく方法。

例えば、1から10までのデータがあった場合に、そこから数をあてる処理を考えます。

二分探索では1から10までの値を 5より大きい値か? → 2より大きい値か? のように絞り込みながら処理を行います。

オーダー: O(log(n))

練習

その1

for i in range(n):
    for j in range(n):
        pass

オーダー: O(n^2)

その3

exist = False # 存在しなかったら false のままになるように初期化
for i in range(n):
    if a[i] == v:
        exist = True
        break

計算量は最悪のケースを考えるべき

オーダー: O(n)

その4

for i in range(0, n, 2):
    print(i, ",", end='')

ループの回数は n/2 （切り下げ）であるが係数 1/2 は無視する。

オーダー: O(n)

その5

for i in range(1, 10):
    for j in range(1, 10):
        print('{} x {} = {}'.format(i, j, i*j))

オーダー: O(n^2)

その6

2次元平面上の座標(x,y)がn個が与えられたとき、2点間の距離が最短となる点の組み合わせと距離を求める。

import math

min_dist = 1000000
for i in range(0, n):
    for j in range(i+1, n):
        if sqrt(x**2 + y**2) < min_dist:
            min_dist = sqrt(x**2 + y**2)

(n-1) + (n-2) + ... + 1 + 0

であるから、初項 n-1, 公差 -1の等差数列と考えて

比較

計算ステップの関係

log(n) < n < n^2 < n^3 < 2^n < n!