Временная сложность в Python 3 - PullRequest
Новая
       3

Временная сложность в Python 3

2 голосов
/ 19 октября 2019

Следующий код работает с проблемой хакерранка: (A и B по умолчанию получат неповторяющиеся и дискретные данные) 

n,m = map(int,input().split())
arr = list(map(int,input().split()))
A = set(map(int,input().split()))
B = set(map(int,input().split()))
count = 0
for x in arr:
    if x in A:
        count+=1
    if x in B:
        count-=1
print(count)

Но следующий код показывает ошибку времени в 4 тестовых случаях: 

n,m = map(int,input().split())
arr = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
count = 0
for x in arr:
    if x in A:
        count+=1
    if x in B:
        count-=1
print(count)

Как резко изменилась сложность времени в списке и наборе и как они работают?

Ответы [ 2 ]

2 голосов
/ 19 октября 2019

set в Python реализован с использованием хеш-таблицы .

Проверка наличия или отсутствия элемента в наборе - это операция O(1) (т.е. с постоянным временем) ивремя выполнения этой проверки не зависит от количества элементов в наборе.

list вместо этого реализовано в виде массива, и для проверки наличия элемента требуется O(n), где n - это числоэлементов в списке. Проверка наличия элемента в списке, содержащем 1000 элементов, займет в десять раз больше времени, чем необходимо, если список содержит только 100 элементов.

0 голосов
/ 19 октября 2019

Изменяются следующие строки: 

A = list(map(int,input().split()))
B = list(map(int,input().split()))

Для хорошего случая вы используете set вместо list. Это влияет, когда вы делаете: 

if x in A:
if x in B:

, потому что это проверяет, есть ли элемент в списке / наборе.

  • Для списков это O (n) потому что вам придется выполнять линейный поиск, поскольку это неупорядоченный контейнер.

  • Для наборов в Python они реализованы с помощью хеш-таблицы, что означает, что вы, скорее всего, будете иметьпросмотр среднего времени (1), но обратите внимание, что в документах не указано, какой тип хэширования используется. Следовательно, вы должны принять наихудший случай O (n).

...