반응형 시간복잡도1 자바 컬렉션(Java Collection)들의 Big O (시간 복잡도, Time Complexity) 자바는 다양한 컬렉션 타입들을 제공한다. 이 컬렉션 타입들은 내부 구현에 따라 다양한 시간 복잡도를 갖는데, 이 특징을 잘 알고 사용해야 불필요한 성능저하를 피할 수 있다. List Add Remove Get Contains Data Structure ArrayList O(1) O(n) O(1) O(n) Array LinkedList O(1) O(1) O(n) O(n) LinkedList CopyonWriteArrayList O(n) O(n) O(1) O(n) Array LinkedList의 시간복잡도에서 remove 연산의 시간복잡도가 O(1)인 이유는 삭제할 엘리먼트에 대한 레퍼런스를 알고 있다고 가정하기 때문에 얻어진 것이다. 만약 삭제할 대상을 탐색하는 동작(get)까지 감안한다면 O(n)이 맞을.. 2019. 5. 31. 이전 1 다음 반응형