Linked List 시간 복잡도
757
작성한 질문수 29
선생님. Linked List의 추가/삭제 시에 노드 간의 데이터 주소만 연결하여 주기만 하면 되기 때문에 시간 복잡도가 O(1)이며, index까지 도달하는데 O(n)의 시간이 걸리기 때문에 추/삭의 경우에도 O(n)의 시간이 걸린다고 볼 수 있다고 하셨는데,, 둘 다 내포한다고 생각하면 되나요??
답변 1
0
사실 코드를 어떻게 작성하냐에 따라서 시간복잡도가 달라질 수 있습니다. 하지만 대부분 linked list 의 장점으로 추/삭 시에 O(1)의 시간복잡도가 걸린다! 라고 면접관과 피면접자간의 합의(?)같은 점들이 있습니다. 하지만 실제 우리가 구현해보면 시간복잡도 O(1)으로 추/삭을 하기에는 현실과 괴리감이 조금 있습니다. 해당 인덱스까지 current node 포인터를 이동시켜야 하기 때문에 실질적인 시간복잡도는 O(n)이라고 볼 수 있는거죠.
물론. current node가 가리키고 있는 동일한 지점에서 지속적인 추/삭이 발생한다면 O(1)이 될 수 있을겁니다. 즉 상황에 따라서, 그리고 코드를 어떻게 구현했냐에 따라서 조금 이론과 다른 지점들이 있습니다.
즉. linked list는 추/삭시에 O(1)의 시간복잡도가 걸리지만, current node 포인터가 해당 index까지 도달해야만 추가/삭제를 할 수 있기 때문에 전체적인 추/삭의 시간복잡도를O(n)으로 볼 수도 있다. 라고 이해하시면 될 것 같아요!
질문에 답이 됐을까요?!
노션 접근이 안됩니다 ㅠㅠ
0
120
2
노션 공유 부탁드립니다.
0
58
2
노션 공유가 안됩니다!
0
152
2
프로세스가 많아질수록 segment table도 많아지는 건가요?
1
73
2
노션 공유가 사라졌습니다.
0
163
2
post 요청
0
56
1
http
0
64
1
mutex, semaphore와 deadllock
0
99
3
실행중인 프로세스는 메모리를 연속적으로? 아니면 불연속적으로 사용하나요?
0
72
1
노션 공유 요청 드립니다.
0
124
1
노션 공유 요청드립니다.
0
87
1
Dynamic Array와 Linked List의 시간복잡도에 대해서..
0
115
1
노션
0
110
1
질문이있습니다 선생님!
0
109
1
질문이있습니다 선생님!
0
99
1
질문이있습니다 선생님!
0
93
1
질문이있습니다 선생님!
0
163
2
질문이있습니다 선생님!
0
152
2
질문이 있습니다 선생님!
1
198
2
질문이 있습니다 선생님!
0
124
1
질문이있습니다 선생님!
0
88
1
질문이 있습니다 선생님!
0
109
1
질문이 있습니다 선생님!
0
91
1
물리적 메모리에 연속적으로 저장하지 않는 이유
0
133
1