Python RU

❓Почему len(list) имеет временную сложность O(1)?

Я столкнулся с простой задачей поиска дубликатов в списке, и хотя решений было много (оптимизированных и неоптимизированных), два из них привлекли мое внимание.

• Первое заключалось в итерации по списку с добавлением каждого элемента в набор. Перед добавлением проверялось, присутствует ли уже данный элемент в наборе, и если да, то получался ответ.

Конечно, при таком решении мы должны были выполнять итерацию по списку, и в худшем случае пришлось бы просматривать весь список.
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
uniqueSet = set()
for i in nums:
if i in uniqueSet:
return True
else:
uniqueSet.add(i)

return False

Тогда наше решение будет зависеть от размера списка: O(n). n – количество элементов в списке.

• В другом решении мы просто сравниваем длину множества списка и длину списка.
len(set(list_name)) == len(list_name)

Учитывая природу множества, которое не может содержать дубликатов, это было бы простым решением. Нам необходимо обратить внимание на функцию len(), которая использовалась для определения длины списка. Эта встроенная функция не зависит от размера списка. Независимо от того, содержит ли ваш список 1 элемент или 1000, согласно стандартной реализации Python (CPython), временная сложность равна O(1).

За счет чего это возможно?

Читать

@pro_python_code

👍6❤5🔥2👎1

www.tgoop.com/pro_python_code/1042

2.86K viewsedited  Jul 17, 2023 at 11:07

❓Почему len(list) имеет временную сложность O(1)?

Я столкнулся с простой задачей поиска дубликатов в списке, и хотя решений было много (оптимизированных и неоптимизированных), два из них привлекли мое внимание.

• Первое заключалось в итерации по списку с добавлением каждого элемента в набор. Перед добавлением проверялось, присутствует ли уже данный элемент в наборе, и если да, то получался ответ.

Конечно, при таком решении мы должны были выполнять итерацию по списку, и в худшем случае пришлось бы просматривать весь список.
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
uniqueSet = set()
for i in nums:
if i in uniqueSet:
return True
else:
uniqueSet.add(i)

return False

Тогда наше решение будет зависеть от размера списка: O(n). n – количество элементов в списке.

• В другом решении мы просто сравниваем длину множества списка и длину списка.
len(set(list_name)) == len(list_name)

Учитывая природу множества, которое не может содержать дубликатов, это было бы простым решением. Нам необходимо обратить внимание на функцию len(), которая использовалась для определения длины списка. Эта встроенная функция не зависит от размера списка. Независимо от того, содержит ли ваш список 1 элемент или 1000, согласно стандартной реализации Python (CPython), временная сложность равна O(1).

За счет чего это возможно?

Читать

@pro_python_code

BY Python RU