반응형
시간복잡도
-
[ 자료구조 ] linked list의 삽입/삭제는 정말 array list보다 빠른가?문득 든 의문점 2023. 1. 5. 22:19
의문점 연결 리스트의 경우 삽입/삭제 자체는 O(1)의 시간 복잡도를 가지지만, 대상이 되는 인덱스 까지 찾아가는 과정을 고려한다면 O(n)의 시간 복잡도가 추가된다고 볼 수 있는데 이를 단순히 O(n + 1)이라 가정한다면 O(n)의 시간 복잡도를 가지는 배열 리스트보다 빠르다고 할 수 없지 않는가? 결론 배열 리스트의 경우 특정 인덱스에 요소를 삽입 / 삭제할 경우 해당 인덱스 이후 모든 요소의 위치를 이동시켜야 한다. 따라서 일정하게 O(n)의 시간 복잡도를 갖는다. 하지만 연결 리스트의 경우 head 부분에 가까워질수록 시간복잡도는 O(1)에 가까워진다. 즉, 삽입/삭제의 대상이 될 인덱스의 위치에 따라 O(1) ~ O(n)의 시간 복잡도를 갖는다. 결론적으로 연결리스트는 배열 리스트보다 빠르거나..