Временная сложность leetcode 287

Question

Если вы перейдете по адресу leetcode.com/problems/find-the-duplicate-number/solution/ (задача 287), будет дано следующее решение:

def findDuplicate(self, nums):
    seen = set()
    for num in nums:
        if num in seen:
            return num
        seen.add(num)

Сложность времени этого решенияуказано как O (n)

Я пытаюсь выяснить, почему это так. Я думаю об этом, если вам дан следующий список:

x = [1,2,3,4,5,6,7,8,9,10,11 ,. ... 98,99,100,100] то есть числа постоянно увеличиваются (или не совпадают) вплоть до дублированного числа в конце массива

Затем, когда вы перебираете каждый элемент, вы получаете постоянно увеличивающийся размернабор для поиска дублирующегося значения. Разве это не будет дольше, чем время O (N)?

В частности, если вы попытаетесь найти 98 в наборе, вам нужно просмотреть 97 (N-4) значений, чтобы увидеть, что его нет вустановить, затем добавить его. Для 99 вы просматриваете 98 значений и т. д. Похоже, что решение O (N ^ 2) в худшем случае?

Answer 1

В некотором смысле, ваше мнение правильно. В качестве примера, пусть найденное число будет 100. Итак, цикл с циклом 'for' будет равен O (n), а затем будет найдено значение в наборе O (n) / O (1).

Средняя сложность времени для нахождения значений в наборе равна O (1), а сложность наихудшего случая - O (n). В этом случае мы имеем сложность наихудшего случая, следовательно, сложность O O (n ^ 2).

Но если вы читаете решение, данное в коде leetcode, они упоминают «амортизированные сложности с постоянным временем», что означает, чтоможет быть худший случай время от времени. Таким образом, они в основном игнорируют это и смотрят на среднюю временную сложность, которая оказывается O (1).

Следовательно, временная сложность составляет O (1).