Guida a Analisi della complessità · 5/6
Per ora questo capitolo è disponibile solo in inglese.
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.
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 callsReturn 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])) # NoneIf 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.
Given a list of integers sorted in ascending order and an integer k ≥ 0, decide whether two elements differ by exactly k. Aim for O(n).
Approach: keep two indices i < j. If the difference is smaller than k, advance j to grow it; if larger, advance i to shrink it. Each index moves at most n times, so the scan is O(n).
def has_pair_with_difference(nums, k):
i, j = 0, 1
while j < len(nums):
if i == j:
j += 1
continue
diff = nums[j] - nums[i]
if diff == k:
return True
if diff < k:
j += 1
else:
i += 1
return False
print(has_pair_with_difference([1, 3, 6, 10, 15], 4)) # True (6, 10)
print(has_pair_with_difference([1, 3, 6, 10, 15], 2)) # True (1, 3)
print(has_pair_with_difference([1, 3, 6, 10, 15], 8)) # FalseGiven a list of length n and q queries (l, r), return the sum of nums[l:r] for each query.
Approach: sum(nums[l:r]) per query costs O(n·q). Build prefix sums once, prefix[i] = nums[0] + ... + nums[i-1], and each query becomes a single subtraction: O(n + q) in total.
from itertools import accumulate
def range_sums(nums, queries):
prefix = [0, *accumulate(nums)]
return [prefix[r] - prefix[l] for l, r in queries]
print(range_sums([3, 1, 4, 1, 5, 9], [(0, 3), (2, 6), (5, 6)])) # [8, 19, 9]Write a function that takes a function and an input generator and estimates the exponent of its growth from the times at n and 2n.
Approach: if T(n) ≈ c·n^k, then T(2n) / T(n) ≈ 2^k, so k ≈ log₂(T(2n) / T(n)). Use the minimum of timeit.repeat to reduce noise.
import math
import timeit
def estimate_exponent(func, make_input, n, number=3):
def best_time(size):
data = make_input(size)
return min(timeit.repeat(lambda: func(data), number=number, repeat=5))
return math.log2(best_time(2 * n) / best_time(n))
def all_pairs(items):
return sum(1 for i in range(len(items)) for j in range(i + 1, len(items)))
print(round(estimate_exponent(sum, lambda n: list(range(n)), 200_000), 1)) # about 1
print(round(estimate_exponent(all_pairs, lambda n: list(range(n)), 1_000), 1)) # about 2in list costs or recursive recurrences.O(n²) or O(n·q) into linear time.
0 commenti
Accedi · Accedi per lasciare un commento.