Set, List 자료형 remove 시간복잡도 O(1), O(n)

릿코드 127. Word Ladder 번 풀다가 list를 굳이 set으로 변환시키길래 중복 제거하려고 했나보다 싶었지만 set 변환 전후로 len()로 비교해보니 중복 자료형이 없었다. 이유는 remove 메소드의 시간복잡도 차이 때문

 

왜 set 자료형과 list 자료형의 remove 메소드 시간 복잡도 차이가 생길까?

 

1. Set 자료형의 remove 메소드 시간복잡도는 O(1)

 

- 알려진 바와 같이 set 자료형은 중복이 불가능하고, 순서가 없다. 

- 또한 값 수정은 불가능하지만 추가(add) 와 삭제(remove)는 가능하다 -> 딕셔너리 자료형의 키 값으로 사용 가능( 딕셔너리 키 값은 수정 불가능)

- 위 특징의 이유는 set 자료형의 경우 hash function에 의해 hash 값을 구하고 해당 값에 해당하는 공간(bucket)에 값을 저장한다 

- 해쉬를 이용하기 때문에 순서가 없고 인덱싱도 없고 중복도 없는 것이며 remove의 시간복잡도가 O(1)이 나오는 것이다. 

 

2. List 자료형의 remove 메소드 시간복잡도는 O(n)

 

- list.remove(x) Remove the first item from the list whose value is x. It is an error if there is no such item.

- 반면 리스트의 경우 찾는 값의 첫 번 째 값을 제거해야 하므로 인덱싱이 필요하다. 

- 첫 번째 값을 제거하면 그 뒤의 값들을 모두 한 칸씩 옮겨줘야 하기 때문에 시간복잡도가 O(n)이 나온다. 

- 값 수정이 가능하기 때문에 딕셔너리 키 값으로도 사용 불가능 

 

따라서 Set이 필요한 순간은 

- 중복된 값을 제거해야 할 때, 순서가 상관이 없을 때

- 빠르게 특정 자료를 찾아내야 할 때