Временная сложность алгоритма#
Примечание
Список#
Operation |
Average Case |
|---|---|
Copy |
O(n) |
Append |
O(1) |
Pop last |
O(1) |
Pop intermediate |
O(n) |
Insert |
O(n) |
Get Item |
O(1) |
Set Item |
O(1) |
Delete Item |
O(n) |
Iteration |
O(n) |
Get Slice |
O(k) |
Del Slice |
O(n) |
Set Slice |
O(k+n) |
Extend |
O(k) |
Sort |
O(n log n) |
Multiply |
O(nk) |
x in s |
O(n) |
min(s), max(s) |
O(n) |
Get Length |
O(1) |
Deque#
Operation |
Average Case |
|---|---|
copy |
O(n) |
append |
O(1) |
appendleft |
O(1) |
pop |
O(1) |
popleft |
O(1) |
extend |
O(k) |
extendleft |
O(k) |
rotate |
O(k) |
remove |
O(n) |
Dict#
Operation |
Average Case |
|---|---|
k in d |
O(1) |
copy |
O(n) |
Get Item |
O(1) |
Set Item |
O(1) |
Delete Item |
O(1) |
Iteration |
O(n) |