Сложность при сравнении двух списков

Question

    for key in string_list:
       if key in new:
          same.append(key)

Мне очень плохо со сложностью, и я стараюсь учиться лучше. Сложность этого кода O(n^2), потому что он сравнивает два списка? Или это O(n) как я только что использовал for l oop? string_list и new - это всего лишь два списка.

Answer 1

Сложность по времени составляет O (n ^ 2), потому что оператор «in» имеет временную сложность O (n) для среднего случая, и у вас уже есть значение для l oop над ним, так что оно становится O (n ^ 2). )

Вы можете сослаться на это:

https://wiki.python.org/moin/TimeComplexity