Какая временная сложность поиска по ключевым значениям словаря при использовании ключа * in *

Question

Вопрос:

Учитывая массив целых чисел, вернуть индексы двух чисел так, чтобы они складывались до определенной цели.

Можно предположить, что каждый вход будет иметь только одно решениеи вы не можете использовать один и тот же элемент дважды.

Мое решение:

То, что я сделал, - это установил словарь и перебрал список заданных чисел (O (n)).Пока я делаю это, я также проверяю, находится ли нужное число в словаре (0 (1)).Таким образом, временная сложность решения составляет O (n).

Мое решение работает, но я новичок в Python и не понимаю временную сложность nums [i] в ​​cache.keys () .При написании кода я думал, что для nums [i] в ​​cache.keys () потребуется O (n) время, чтобы найти nums [i] в ​​списке ключей, что усложнит временную сложность O (n).^ 2).Но результаты моего решения выглядят так, как будто оно обходится за O (n) времени.Это заставляет меня поверить, что nums [i] в ​​cache.keys () занимает O (1) время.Мне было интересно, если это правильно, и если кто-то может объяснить, как это происходит.

    def twoSum(self, nums, target):
        cache = {}
        for i in range(len(nums)):
            b = target - nums[i]

            if nums[i] in cache.keys():
                return [i, cache[nums[i]]]

            cache[b] = i;

результаты во время выполнения

Спасибо:)

Answer 1

Словари реализованы в виде хеш-таблиц / карт, которые имеют среднюю O (1) производительность для поиска. Внутренне они имеют ту же реализацию, что и set s.

Для дальнейшего улучшения производительности замените

if nums[i] in cache.keys():

с

if nums[i] in cache:

---

Кроме того, вы можете сделать улучшение с помощью enumerate (что более Pythonic):

def twoSum(self, nums, target):
    cache = {}
    for i, x in enumerate(nums):
        b = target - x

        if x in cache:
            return [i, cache[x]]

        cache[b] = i;