Wydajność operacji na typach wbudowanych¶
Notacja “Big O”¶
Notacja O pozwala na zwięzłe opisanie, jak szybko wykonuje się dana operacja. Zapis O(1) oznacza, że dana operacja będzie wykonywała się zawsze tak samo długo, niezależnie od tego, jak duża jest kolekcja. Zapis O(n) oznacza, że czas wykonania danej operacji zależy liniowo od wielkości kolekcji. Na przykład, na pustej liście może ona zająć średnio 50 mikrosekund, na jednoelementowej 60 mikrosekund, na dwuelementowej 70 mikrosekund itd.
Wbudowane algorytmy - lista¶
Operation |
Average Case |
Amortized Worst Case |
|---|---|---|
Copy |
O(n) |
O(n) |
Append[1] |
O(1) |
O(1) |
Insert |
O(n) |
O(n) |
Get Item |
O(1) |
O(1) |
Set Item |
O(1) |
O(1) |
Delete Item |
O(n) |
O(n) |
Iteration |
O(n) |
O(n) |
Get Slice |
O(k) |
O(k) |
Del Slice |
O(n) |
O(n) |
Set Slice |
O(k+n) |
O(k+n) |
Extend[1] |
O(k) |
O(k) |
Sort |
O(n log n) |
O(n log n) |
Multiply |
O(nk) |
O(nk) |
x in s |
O(n) |
O(n) |
min(s), max(s) |
O(n) |
O(n) |
Get Length |
O(1) |
O(1) |
k oznacza wielkość wycinka.
Wbudowane algorytmy - słownik¶
Operation |
Average Case |
Amortized Worst Case |
|---|---|---|
Copy[2] |
O(n) |
O(n) |
Get Item |
O(1) |
O(n) |
Set Item[1] |
O(1) |
O(n) |
Delete Item |
O(1) |
O(n) |
Iteration[2] |
O(n) |
O(n) |
[1] = Pojedyncza operacja może trwać długo, w zależności od poprzednich wartości słownika
[2] = Dla tych operacji n oznacza największą pojemność, jaką kiedykolwiek osiągnął słownik, a nie bieżącą.
Wbudowane algorytmy - zbiór¶
Operation |
Average Case |
Amortized Worst Case |
|---|---|---|
x in s |
O(1) |
O(n) |
Union s|t |
O(len(s)+len(t)) |
O(len(s)+len(t)) |
Intersection s&t |
O(min(len(s), len(t)) |
O(len(s) * len(t)) |
Difference s-t |
O(len(s)) |
O(len(s)) |
s.difference_update(t) |
O(len(t)) |
O(len(t)) |