理解度チェック

Big-O計算量あてクイズ

コード片を見て、その時間計算量を当てる12問です。O(1) から O(2ⁿ) まで、ループの数え方・ネスト・再帰の広がりを、理由つきで身につけられます。

Q1 / 12正解 0

Pythonこの関数の時間計算量は？

def total(arr):
    s = 0
    for x in arr:      # n回
        s += x
    return s

計算量を読む3つのコツ

ネストは掛け算、並列は足し算。ループの中のループは n × n = O(n²)。ネストでない2つのループは n + n = O(n)（定数倍は無視）。
半分ずつ減るなら対数。毎回 n が半分になる処理（二分探索・木の高さ）は O(log n)。分岐が2倍に広がる再帰は逆に O(2ⁿ)。
支配項だけ残す。O(n² + n) は O(n²)、O(2n) は O(n)。n が大きいときに効く一番強い項だけを見る。