Guida a Analisi della complessità · 3/6
Per ora questo capitolo è disponibile solo in inglese.
We write O(n) linear search, O(log n) binary search and O(n²) pair counting in Python, time them with timeit, then port an O(n²) and an O(n) two-sum to C++, Java and TypeScript.
import timeit
def linear_search(items, target): # O(n)
for i, x in enumerate(items):
if x == target:
return i
return -1
def binary_search(items, target): # O(log n), sorted input
lo, hi = 0, len(items)
while lo < hi:
mid = (lo + hi) // 2
if items[mid] < target:
lo = mid + 1
else:
hi = mid
if lo < len(items) and items[lo] == target:
return lo
return -1
def count_pairs_with_sum(items, target): # O(n²)
count = 0
n = len(items)
for i in range(n):
for j in range(i + 1, n):
if items[i] + items[j] == target:
count += 1
return countlinear_search scans from the front: worst case Θ(n).binary_search keeps the range [lo, hi) and discards half of it per iteration, about log₂ n + 1 times. Then lo is the first index not less than the target (like bisect.bisect_left).count_pairs_with_sum checks every pair i < j: n(n-1)/2 comparisons, Θ(n²).timeit runs code many times with garbage collection off. Use repeat and keep the minimum; the rest is mostly noise.
def bench(func, *args, number=100, repeat=7):
timer = timeit.Timer(lambda: func(*args))
return min(timer.repeat(repeat=repeat, number=number)) / number
for n in (1_000, 2_000, 4_000):
data = list(range(n))
lin = bench(linear_search, data, -1) # worst case
bi = bench(binary_search, data, -1)
pairs = bench(count_pairs_with_sum, data, -1, number=1, repeat=5)
print(n, f"{lin:.2e} {bi:.2e} {pairs:.2e}")Sample run:
| n | Linear | Binary | Pairs |
|---|---|---|---|
| 1,000 | 35.6 µs | 0.78 µs | 26.7 ms |
| 2,000 | 75.7 µs | 0.99 µs | 115.2 ms |
| 4,000 | 164.2 µs | 0.91 µs | 528.1 ms |
Doubling n doubles linear search, quadruples pair counting, and binary search stays flat. This doubling experiment is the simplest check: a ratio of 2 means , 4 means , 8 means .
nn²n³Find two indices whose values sum to target. Checking every pair is O(n²); a hash map of seen values makes it one O(n) pass on average.
def two_sum_quadratic(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
return None
def two_sum_linear(nums, target):
seen = {} # value -> first index
for j, x in enumerate(nums):
i = seen.get(target - x)
if i is not None:
return i, j
seen.setdefault(x, j)
return None
nums = [8, 3, 11, 5, 2]
print(two_sum_quadratic(nums, 13), two_sum_linear(nums, 13)) # (0, 3) (0, 3)With several answers, the pairs found may differ.
#include <iostream>
#include <optional>
#include <unordered_map>
#include <utility>
#include <vector>
using Pair = std::optional<std::pair<int, int>>;
// O(n^2)
Pair twoSumQuadratic(const std::vector<int>& nums, int target) {
for (std::size_t i = 0; i < nums.size(); ++i)
for (std::size_t j = i + 1; j < nums.size(); ++j)
if (nums[i] + nums[j] == target) return std::make_pair(int(i), int(j));
return std::nullopt;
}
// O(n) average
Pair twoSumLinear(const std::vector<int>& nums, int target) {
std::unordered_map<int, int> seen; // value -> first index
for (std::size_t j = 0; j < nums.size(); ++j) {
auto it = seen.find(target - nums[j]);
if (it != seen.end()) return std::make_pair(it->second, int(j));
seen.emplace(nums[j], int(j));
}
return std::nullopt;
}
int main() {
if (auto r = twoSumLinear({8, 3, 11, 5, 2}, 13)) std::cout << r->first << ' ' << r->second << '\n'; // 0 3
}import java.util.HashMap;
import java.util.Map;
public class TwoSum {
// O(n^2)
static int[] twoSumQuadratic(int[] nums, int target) {
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[i] + nums[j] == target) return new int[] {i, j};
return null;
}
// O(n) average
static int[] twoSumLinear(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>(); // value -> first index
for (int j = 0; j < nums.length; j++) {
Integer i = seen.get(target - nums[j]);
if (i != null) return new int[] {i, j};
seen.putIfAbsent(nums[j], j);
}
return null;
}
public static void main(String[] args) {
int[] r = twoSumLinear(new int[] {8, 3, 11, 5, 2}, 13);
System.out.println(r[0] + " " + r[1]); // 0 3
}
}// O(n^2)
function twoSumQuadratic(nums: number[], target: number): [number, number] | null {
for (let i = 0; i < nums.length; i++)
for (let j = i + 1; j < nums.length; j++)
if (nums[i] + nums[j] === target) return [i, j];
return null;
}
// O(n) average
function twoSumLinear(nums: number[], target: number): [number, number] | null {
const seen = new Map<number, number>(); // value -> first index
for (let j = 0; j < nums.length; j++) {
const i = seen.get(target - nums[j]);
if (i !== undefined) return [i, j];
if (!seen.has(nums[j])) seen.set(nums[j], j);
}
return null;
}
const nums = [8, 3, 11, 5, 2];
console.log(twoSumQuadratic(nums, 13), twoSumLinear(nums, 13)); // [ 0, 3 ] [ 0, 3 ]O(n), O(log n) and O(n²) show up as about 2x, flat and about 4x.timeit; keep the minimum of several runs.O(n) memory to turn O(n²) into O(n).
0 commenti
Accedi · Accedi per lasciare un commento.