Почему производительность равна нулю для следующей логики?

Question

Я написал эту функцию для удобства и получил 0 в производительности и 100% за правильность.

A = [-1, -3]
B = [1,2,3]
C = [1,4,5,6,77,2]

Предполагается, что приведенная ниже функция возвращает наименьшее целое число, но не представляет переданный ей список int.

def solution(A):
    temp = 0;
    tempLst = []
    for item in A:
        temp = temp+1
        if temp not in A:
            tempLst.append(temp)

    return min(tempLst) if tempLst else max(A) + 1

почему это так? Все, что я хотел, это сделать без кучи, itertools, частично.

Answer 1

У вас есть то, что фактически является вложенным циклом.

for item in A:

Эта линия проходит по всем элементам A,

    if temp not in A:

... и для каждого из этих элементов вы повторяете цикл, сравнивая temp к каждому элементу A,

Время выполнения этого кода является квадратичным по размеру A, Например, если A имеет 1000 элементов, этот код занимает 1000*1000 = 1 000 000 шагов для завершения.