Daniel's blog

변수나 자료형 등이 중복으로 나타나는지와 같은 확인을 위해 'in'이라는 키워드를 많이 사용한다. 이때 Set와 List 중 어떤 것을 사용하느냐에 따라 속도의 차이가 매우 커질 수 있다. Set가 List에 비해 일반적으로 빠른 성능을 보이는데 이는 Set가 Hash Table로 구현이 돼있는 반면, List는 배열로 구현돼있기 때문이다. Hash Table의 경우 검색(lookup), 삽입(isertion), 삭제(deletion)에 대해 O(1)의 시간 복잡도를 갖지만, 배열의 경우 O(n) 을 갖기 때문이다. 아래 코드를 통해 시간의 차이를 확인할 수 있다. import time my_list = list(range(1000000)) my_set = set(my_list) start_time = ..

Hash에서 특정 key에 대한 value를 확인할 때 걸리는 시간 복잡도가 O(1) - Constant time 이라는 것에 대한 이해가 되지 않아 확인해보니 실제로는 O(1)보다는 오래 걸리지만 거의 그 즈음 걸리기에 O(1)으로 표기한다는 것을 알았다. 내가 잘못 이해하고 있었던 부분은 Search와 Index(Access)의 차이다. Search는 한 자료 구조(Data Structure) 안에서 특정 요소(element)를 검색하는 것을 의미하는 반면, Index(Access)는 이미 어디 있는지 알고 이를 접근한다는 차이를 가지고 이해를 해야했다. List의 경우에도 Index를 알고 있다면 바로 접근이 가능 하기에 O(1)의 시간 복잡도를 갖지만, 특정 데이터(data)를 검색한다는 것은 L..