[Algorithm] List, Dictionary의 시간 복잡도
Contents 코딩 테스트를 하다보면 시간 복잡도를 고려하지 않아서 발생하는 시간 초과 문제에 직면할 때가 있다. 코딩 테스트에서는 리스트(List) 구조를 많이 사용하는데, 리스트에 사용할 수 있는 함수 혹은 주요 연산들의 시간 복잡도가 어느 정도인지 알아보자. List 연산 시간 복잡도 설명 O(1) 전체 요소의 개수를 리턴한다. O(1) index 의 요소를 가져온다. O(k) index 부터 까지의 길이만큼 개 요소를 가져온다. 객체 개에 대한 조회가 필요하기 때문에 O() O(n) 요소가 존재하는지 확인하는 경우 순차 탐색을 해야하기 때문..