計算量解析ガイド · 5/6

Practice Problems

この章は現在、英語でのみ提供しています。

Complexity analysis gets faster with practice. These five problems train reading a complexity, improving it, and confirming it by measurement. Try each one before reading the approach and solution.

Problem 1. Name the complexity

Give the time complexity of each function. In c, result is a list.

def a(n):
    total, i = 0, 1
    while i < n:
        for _ in range(n):
            total += 1
        i *= 2
    return total

def b(n):
    total = 0
    for _ in range(n):
        j = 1
        while j * j <= n:
            total += 1
            j += 1
    return total

def c(items):
    result = []
    for x in items:
        if x not in result:
            result.append(x)
    return result

def d(n):
    if n <= 1:
        return 1
    return d(n // 2) + d(n // 2)

Approach: count outer and inner iterations separately and multiply; write a recurrence for recursion.

a: i doubles, so the outer loop runs about log n times around an inner loop of n. O(n log n)
b: the inner loop runs while j ≤ √n, so O(n√n), that is O(n^1.5)
c: x not in result scans the list. With all values distinct that is 0 + 1 + ... + (n-1) comparisons, O(n²). Adding a set makes it O(n).
d: it looks logarithmic, but T(n) = 2T(n/2) + O(1) is O(n) by the master theorem. Counting calls confirms it:

calls = 0

def d_counted(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return d_counted(n // 2) + d_counted(n // 2)

for n in (1_024, 2_048, 4_096):
    calls = 0
    d_counted(n)
    print(n, calls)   # 2047, 4095, 8191: twice the n, twice the calls

Problem 2. First repeated value

Return the value whose second occurrence comes earliest, or None. In [4, 7, 1, 7, 4] the answer is 7, because 7 repeats before 4 does.

Approach: comparing all pairs is O(n²). Scan once and keep seen values in a set; set lookups are O(1) on average, so the whole scan is O(n) time and O(n) space.

def first_repeat(items):
    seen = set()
    for x in items:
        if x in seen:
            return x
        seen.add(x)
    return None

print(first_repeat([4, 7, 1, 7, 4]))  # 7
print(first_repeat([1, 2, 3]))        # None

If memory is tight and you only need to know whether any duplicate exists, sort and compare neighbours in O(n log n) time instead. Pick based on whether time or memory is scarcer.

この章について質問がありますか？

Practice Problems

Problem 1. Name the complexity

Problem 2. First repeated value

Problem 3. A pair with difference k

Problem 4. Range sum queries

Problem 5. Estimate the exponent by measuring

Summary

コメント 0件