Пространственная сложность и компромиссы

Что измеряет пространственная сложность

# 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]

Память стека вызовов при рекурсии

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)

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)

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

# 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]

Память при мемоизации и табуляции

# 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)

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']))

Анализ памяти алгоритмов на графах

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]

Проблемы с выделением памяти для строк и массивов

# 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]

Распознавание компромиссов по памяти на собеседованиях

# 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

Шаблон формулировки полной сложности

# 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]]

Быстрая проверка

Итоги урока