Python 基本型態搜尋的時間複雜度
2022 年 5 月 11 日
list
python的列表內部實現是數組，超過容量會增加更多的容量。
| Operation | Average Case | Amortized Worst Case |
|---|---|---|
| Append[1] | O(1) | O(1) |
| Insert | O(n) | O(n) |
| Get Item | O(1) | O(1) |
| Delete Item | O(n) | O(n) |
| Iteration | O(n) | O(n) |
| Del Slice | O(n) | O(n) |
| Sort | O(n log n) | O(n log n) |
| x in s | O(n) | O(n) |
| Get Length | O(1) | O(1) |
dict
| Operation | Average Case | Amortized Worst Case |
|---|---|---|
| Set Item[1] | O(1) | O(n) |
| Get Item | O(1) | O(n) |
| Delete Item | O(1) | O(n) |
| Iteration[2] | O(n) | O(n) |
| x in s | O(1) | O(n) |
set
| Operation | Average Case | Amortized Worst Case |
|---|---|---|
| Iteration[2] | O(n) | O(n) |
| x in s | O(1) | O(n) |
