Coding Interview Prep · レッスン

空間計算量とトレードオフ

コールスタックと補助データ構造に必要な補助領域を測定し、メモ化やin-placeアルゴリズムにおける時間と空間のトレードオフを理解します。

レッスン 4/413 ステップ

「空間計算量とトレードオフ」はCoddyKit上の無料Coding Interview Prepレッスンです。これはレッスン4/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

空間計算量は何を測るのか

空間計算量は、入力以外に必要な追加メモリを測定します。これは補助領域と呼ばれます。変数が少数ならO(1)、結果を格納する配列やハッシュマップならO(n)です。コードを確認してください。

# O(1) auxiliary space
def sum_array(nums):
    total = 0       # one integer variable
    for n in nums:
        total += n  # constant extra space
    return total

# O(n) auxiliary space
def copy_array(nums):
    return list(nums)  # allocates n slots

print(sum_array([1, 2, 3, 4]))  # 10
print(copy_array([1, 2, 3, 4]))  # [1, 2, 3, 4]

再帰におけるコールスタックの領域

再帰呼び出しごとにスタックフレームが追加されるため、深さによって必要な領域が決まります。線形再帰はO(n)、平衡木のDFSはO(log n)です。反復処理に書き換えると、領域をより適切に制御できます。

import sys

def recursive_sum(n):
    if n == 0: return 0
    return n + recursive_sum(n - 1)
# Space: O(n) stack frames

def iterative_sum(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total
# Space: O(1)

print(recursive_sum(100))   # 5050
print(iterative_sum(100))   # 5050

マージソートの領域: O(n)

マージソートでは、一時配列のためにO(n)の追加領域が必要です。これは、安定したO(n log n)のソートの代償です。ヒープソートは領域を節約できますが、安定ソートではありません。コードを確認してください。

import tracemalloc

tracemalloc.start()

def merge_sort(arr):
    if len(arr) <= 1: return arr
    m = len(arr) // 2
    l = merge_sort(arr[:m])    # new list
    r = merge_sort(arr[m:])    # new list
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: out.append(l[i]); i+=1
        else:             out.append(r[j]); j+=1
    return out + l[i:] + r[j:]

data = list(range(1000, 0, -1))
merge_sort(data)
_, peak = tracemalloc.get_traced_memory()
print(f'Peak memory: {peak} bytes')  # proportional to n

インプレースアルゴリズム: O(1)領域

インプレースアルゴリズムは、比例して増加する追加領域を使わず、入力を直接変更します。たとえば、2つのポインターを使って配列を反転する処理です。これにより、空間計算量をO(1)に保てます。コードを確認してください。

def reverse_inplace(arr):
    l, r = 0, len(arr) - 1
    while l < r:
        arr[l], arr[r] = arr[r], arr[l]  # swap
        l += 1
        r -= 1
    # Space: O(1) -- only two pointer variables

def rotate_right(arr, k):
    '''Rotate array right by k positions in-place.'''
    n = len(arr)
    k %= n
    arr.reverse()          # O(1) space
    arr[:k] = arr[:k][::-1]
    arr[k:]  = arr[k:][::-1]

a = [1, 2, 3, 4, 5]
rotate_right(a, 2)
print(a)  # [4, 5, 1, 2, 3]

時間と空間のトレードオフ: Two Sum

時間と空間のトレードオフは、至るところにあります。Two Sumは、O(1)の空間でO(n^2)の時間に解くことも、ハッシュマップを使ってO(n)の空間でO(n)の時間に解くこともできます。両方を説明し、どちらをより重視するか確認してください。

# O(n^2) time, O(1) space
def two_sum_slow(nums, target):
    for i in range(len(nums)):          # O(n)
        for j in range(i+1, len(nums)): # O(n)
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# O(n) time, O(n) space
def two_sum_fast(nums, target):
    seen = {}                    # O(n) space
    for i, n in enumerate(nums):
        comp = target - n
        if comp in seen:         # O(1) lookup
            return [seen[comp], i]
        seen[n] = i
    return []

print(two_sum_fast([2, 7, 11, 15], 9))  # [0, 1]

メモ化と表形式化の領域比較

トップダウンのメモ化では、O(n)のメモ領域とO(n)のスタック領域が必要です。ボトムアップの表形式化では、スタックを使いません。最後の数行だけを保持すれば、領域をO(1)まで削減できます。これが空間最適化DPです。

# Fibonacci: O(n) space with full table
def fib_table(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# O(1) space: keep only last two values
def fib_optimal(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_table(10))    # 55
print(fib_optimal(10))  # 55

ハッシュマップの領域: O(n)

ハッシュマップは、解法でよく登場するO(n)の空間コストです。訪問済み要素を管理する集合や、個数を数える頻度マップなどに使われます。必ず示してください。「時間O(n)、空間O(n)」が完全な回答です。

def contains_duplicate(nums):
    # O(n) time, O(n) space
    seen = set()
    for n in nums:
        if n in seen: return True
        seen.add(n)
    return False

def group_anagrams(words):
    # O(n*m) time, O(n) space  (m = avg word length)
    from collections import defaultdict
    groups = defaultdict(list)
    for w in words:
        groups[tuple(sorted(w))].append(w)
    return list(groups.values())

print(contains_duplicate([1,2,3,1]))  # True
print(group_anagrams(['eat','tea','tan','ate','nat','bat']))

グラフアルゴリズムの空間分析

グラフには実際に領域が必要です。隣接リストはO(V + E)、BFSで使う訪問済み集合とキューはO(V)、DFSの再帰の深さはO(V)です。グラフの空間計算量はVとEを使って示してください。

from collections import deque

def bfs(graph, start):
    # Space: O(V) for visited set + O(V) for queue
    visited = set()      # O(V)
    queue = deque([start])  # O(V) max
    order = []
    while queue:
        node = queue.popleft()
        if node in visited: continue
        visited.add(node)
        order.append(node)
        for nb in graph.get(node, []):
            queue.append(nb)
    return order

g = {0:[1,2], 1:[3], 2:[3], 3:[]}
print(bfs(g, 0))  # [0, 1, 2, 3]

文字列と配列の割り当てに関する落とし穴

隠れたメモリ割り当てによって、空間計算量がO(n)になることがあります。スライスは新しいリストを作り、ループ内で文字列に+を使うとO(n^2)になります。sorted()はコピーを作りますが、lst.sort()はその場で処理します。コードを確認してください。

# Hidden allocations:
nums = [1, 2, 3, 4, 5]

# Creates a NEW list -- O(n) space
slice_copy = nums[1:4]  # [2, 3, 4]

# Creates a NEW sorted list -- O(n) space
sorted_copy = sorted(nums)  # nums unchanged

# Sorts IN PLACE -- O(1) extra space
nums.sort()

print(slice_copy)   # [2, 3, 4]
print(sorted_copy)  # [1, 2, 3, 4, 5]
print(nums)         # [1, 2, 3, 4, 5]

面接で空間のトレードオフを見抜く

最初に空間計算量を伝えてください。面接官がより少ない領域を求める場合は、メモ化の代わりにボトムアップDPを使う、ハッシュマップの代わりにインプレースソートを使う、といった方法があります。コードを確認してください。

# Problem: find if array has duplicates
# Option 1: O(1) time-per-check, O(n) space
def has_dup_hash(nums):
    return len(nums) != len(set(nums))

# Option 2: O(n log n) time, O(1) extra space
def has_dup_sort(nums):
    nums_copy = sorted(nums)  # O(n) space -- still!
    for i in range(1, len(nums_copy)):
        if nums_copy[i] == nums_copy[i-1]:
            return True
    return False

# Option 3: truly O(1) extra -- sort in-place
def has_dup_inplace(nums):
    nums.sort()               # modifies original
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]: return True
    return False

計算量を説明する定型文

必ず完全な説明をしてください。時間と空間の両方を示します。「時間O(n)、追加領域O(1)です」のように伝えてください。トレードオフがある場合は、それにも触れます。これが、上級者の候補者を際立たせます。

# Complete complexity example: Merge Intervals
def merge_intervals(intervals):
    # Time: O(n log n) for sort + O(n) for merge = O(n log n)
    # Space: O(n) for output (could be n/2 to n intervals)
    intervals.sort(key=lambda x: x[0])  # O(n log n)
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]

クイックチェック

クイックチェックです。空間計算量についての考え方がどれだけ身に付いたか確認しましょう。準備はできています。✅

対話的なレッスンで答える

レッスンの振り返り

振り返り: 補助領域は入力とは別に数えます。再帰はO(深さ)のスタック領域を使用し、時間と空間のトレードオフがアルゴリズム設計における多くの選択を左右します。

無料で開始

AI チューターと学ぶ Coding Interview Prep — 無料

ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。

コース: 90
レッスン: 360

無料で学習を始めるコース全体を表示

よくある質問

「空間計算量とトレードオフ」レッスンは無料ですか？

はい。「空間計算量とトレードオフ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「空間計算量とトレードオフ」で何を学びますか？

コールスタックと補助データ構造に必要な補助領域を測定し、メモ化やin-placeアルゴリズムにおける時間と空間のトレードオフを理解します。ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン4/4です。

「空間計算量とトレードオフ」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← Coding Interview Prepに戻る