PRO_PYTHON_CODE Telegram 1042
Почему 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
👍65🔥2👎1



tgoop.com/pro_python_code/1042
Create:
Last Update:

Почему 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


Share with your friend now:
tgoop.com/pro_python_code/1042

View MORE
Open in Telegram


Telegram News

Date: |

Members can post their voice notes of themselves screaming. Interestingly, the group doesn’t allow to post anything else which might lead to an instant ban. As of now, there are more than 330 members in the group. The public channel had more than 109,000 subscribers, Judge Hui said. Ng had the power to remove or amend the messages in the channel, but he “allowed them to exist.” Matt Hussey, editorial director at NEAR Protocol also responded to this news with “#meIRL”. Just as you search “Bear Market Screaming” in Telegram, you will see a Pepe frog yelling as the group’s featured image. How to Create a Private or Public Channel on Telegram? Telegram is a leading cloud-based instant messages platform. It became popular in recent years for its privacy, speed, voice and video quality, and other unmatched features over its main competitor Whatsapp.
from us


Telegram Python RU
FROM American