파이썬에서 목록을 집합으로 변환하면 실행 시간과 공간의 복잡도는 어떻게됩니까?목록을 파이썬에서 설정하도록 변환하는 실행 시간
Example:
data = [1,2,3,4,5,5,5,5,6]
# this turns list to set and overwrites the list
data = set(data)
print data
# output will be (1,2,3,4,5,6)
목록을 집합으로 변환하려면 목록의 모든 항목을 O (n) 번 방문해야합니다. 요소를 집합에 삽입하는 것은 O (1)이므로 전체 시간 복잡도는 O (n)이됩니다.
새 집합에 필요한 공간이 목록의 길이보다 작거나 같으면 O (n)이기도합니다.
파이썬 데이터 구조에 대해서는 reference이 좋습니다.
당신은 O (N) 시간 전체리스트를 통해 반복하고, 그 다음 1 시간 O 인 세트에 각각 삽입한다. 따라서 전체 시간 복잡도는 O (n)입니다. 여기서 n은 목록의 길이입니다.
집합 이외의 다른 공간을 만들거나 사용중인 목록이 필요하지 않습니다.