Python-un daxili tiplərini bilmədən alqoritmin real mürəkkəbliyini hesablamaq olmaz: bir sətir x in a siyahı üçün O(n), çoxluq üçün isə O(1) ola bilər. Aşağıdakı cədvəllər CPython-un sənədləşdirilmiş davranışına (python.org-dakı TimeComplexity səhifəsi) əsaslanır və hər iddianı kiçik ölçmə ilə yoxlayacağıq.
list
| Əməliyyat | Qiymət |
|---|---|
a[i], a[i] = x, len(a) | O(1) |
a.append(x), a.pop() | O(1) (append amortizə) |
a.insert(i, x), a.pop(i), a.pop(0), del a[i] | O(n) — elementlər sürüşür |
x in a, a.index(x), a.count(x), a.remove(x) | O(n) |
a[i:j], a.copy() | O(j - i), O(n) — kopya |
a.extend(b), a + b | O(len(b)), O(len(a) + len(b)) |
min(a), max(a), sum(a), a.reverse() | O(n) |
a.sort(), sorted(a) | O(n log n), sıralı girişdə O(n) |
from timeit import timeit
n = 100_000
data = list(range(n))
at_end = timeit(lambda: (data.append(0), data.pop()), number=2000)
at_front = timeit(lambda: (data.insert(0, 0), data.pop(0)), number=2000)
print("front is much slower than end:", at_front > 5 * at_end)front is much slower than end: True