В данной статье рассмотрим сложность основных операций, в нотации O (О большое) при работе с различными коллекциями значений в Python.
Сложность операций с списками и кортежами
Большинство операций со списком и кортежем имеют сложность O(N). Рассмотрим основные из них:
- len(lst) - O(1)
- lst.append(5) - O(1)
- del lst[i] - O(N)
- lst.remove(...) - O(N)
- lst.reverse() - O(N)
- lst.sort() - O(N log N)
- lst.pop() - O(1)
Сложность операций с множествами
По сравнению со списком и кортежем множества большую часть операций выполняют со сложностью O(1). Рассмотрим основные из них:
- len(s) - O(1)
- s.add(5) - O(1)
- s.remove(5) - O(1)
- s.pop(i) - O(1)
- s.clear() - O(1)
Здесь важно отметить, что операции удаления в множестве происходят быстрее, чем в списке.
Сложность операций со словарями
Большинство операций словарей имеет сложность O(1). Рассмотрим основные из них:
- d[k] - O(1)
- d[k] = v - O(1)
- len(d) - O(1)
- del d[k] - O(1)
- d.keys() - O(1)
- d.pop(k) - O(1)
Заключение
Важно выбирать структуру данных, которая была бы оптимальной для конкретной задачи.
Например, если ожидается, что программа будет осуществлять частый поиск информации, словарь подойдет лучше. Но при этом, если необходимо просто хранить упорядоченный набор данных, то правильнее выбрать словарь или кортеж.
Например, если ожидается, что программа будет осуществлять частый поиск информации, словарь подойдет лучше. Но при этом, если необходимо просто хранить упорядоченный набор данных, то правильнее выбрать словарь или кортеж.