Guida a Strutture dati di base · 4/6
Per ora questo capitolo è disponibile solo in inglese.
Big-O tells you how cost grows with n, the number of stored items. For basic data structures the interesting part is that the same operation can be O(1) on one structure and O(n) on another, and that some O(1) figures are averages or amortized rather than guaranteed.
| Operation | Dynamic array | Linked list (doubly) | Deque (ring buffer) | Hash table |
|---|---|---|---|---|
| Access k-th item | O(1) | O(n) | O(1) | not supported |
| Search by value | O(n) | O(n) | O(n) | O(1) average by key |
| Insert / delete at end | O(1) amortized | O(1) | O(1) amortized | n/a |
| Insert / delete at front | O(n) | O(1) | O(1) amortized | n/a |
| Insert / delete in the middle | O(n) | O(1) once the node is found | O(n) | n/a |
| Insert / delete by key | n/a | n/a | n/a | O(1) average, O(n) worst |
| Extra memory per item | small (spare capacity) | two pointers per node | small | bucket array plus chain nodes |
Stacks and queues are restrictions of these structures, so a stack on a dynamic array has O(1) amortized push and pop, and a queue on a ring buffer or linked list has O(1) enqueue and dequeue.
A single append to a full dynamic array copies all n items, which is O(n). Over a sequence of n appends with doubling, the copies are 1 + 2 + 4 + ... + n/2 + n, which is less than 2n. Total work is O(n), so the cost per append is O(1) amortized.
The growth factor matters. Growing by a constant amount (say 10 slots each time) makes the copies 10 + 20 + 30 + ..., which is O(n squared) in total. Any constant multiplier greater than 1 keeps appends O(1) amortized; libraries trade memory for speed by choosing 1.5, 2 or a small over-allocation as CPython does.
def total_copies(n, grow):
size, cap, copies = 0, 1, 0
for _ in range(n):
if size == cap:
copies += size
cap = grow(cap)
size += 1
return copies
n = 100_000
print("x2 :", total_copies(n, lambda c: c * 2)) # about 1.3 * n
print("x1.5 :", total_copies(n, lambda c: c + c // 2 + 1))
print("+10 :", total_copies(n, lambda c: c + 10)) # about n * n / 20With m buckets and n keys, the load factor is alpha = n / m. If the hash function spreads keys evenly, the expected chain length is alpha, so a lookup costs O(1 + alpha). Keeping alpha below a constant (0.75 in Java's HashMap, 1.0 by default in C++'s std::unordered_map) makes it O(1) on average. Resizing costs O(n) when it happens, but like array growth it is O(1) amortized per insert.
The worst case is O(n): if every key lands in one bucket, the table degenerates into a list. This happens with a poor hash function or with adversarial input crafted to collide (hash flooding). Python randomizes string hashes per process for this reason, and Java's HashMap turns very long chains into balanced trees so the worst case becomes O(log n).
Complexity tables are easy to verify with a timer. Removing from the front is the classic trap:
from collections import deque
from timeit import timeit
def drain_list(n):
items = list(range(n))
while items:
items.pop(0) # shifts every remaining item
def drain_deque(n):
items = deque(range(n))
while items:
items.popleft() # moves one index
n = 100_000
print("list.pop(0) ", timeit(lambda: drain_list(n), number=1))
print("deque.popleft()", timeit(lambda: drain_deque(n), number=1))The list version is quadratic in total and at this size is often a hundred times slower or more. Membership tests show the hash table advantage:
from timeit import timeit
items = list(range(10_000))
as_set = set(items)
probes = range(0, 20_000, 7)
print("list:", timeit(lambda: sum(p in items for p in probes), number=1))
print("set :", timeit(lambda: sum(p in as_set for p in probes), number=1))| Type | Operation | Average cost |
|---|---|---|
list | x[i], append, pop() | O(1) (append amortized) |
list | insert(0, x), pop(0), x in list | O(n) |
deque | append, appendleft, pop, popleft | O(1) |
deque | d[i] in the middle | O(n) |
dict / set | get, set, delete, in | O(1) average, O(n) worst |
All five structures use O(n) space, but the constants differ. A dynamic array may hold up to about twice the slots it needs right after growing. A doubly linked list stores two pointers per item, which on a 64-bit machine is 16 bytes of overhead before counting the value. Hash tables cap the load factor at a limit such as 0.75 or 1, so many buckets stay empty, and chaining adds a node per entry.
Arrays give O(1) indexing and amortized O(1) appends, linked structures give O(1) splicing at known positions, and hash tables give O(1) average key operations with an O(n) worst case. Amortized and average figures are reliable in practice as long as growth is geometric and the hash function spreads keys well; measure when in doubt.
0 commenti
Accedi · Accedi per lasciare un commento.