질문이있습니다 선생님!
105
30 asked
링크드리스트의 경우
어레이에 비하면 cud의 시간복잡도가 더 좋아서 O(1)이라고 해주셨는데요,
( 해당 노드 참조주소만 바꾸면되니까 )
근데 생각해보면 n번째 노드 다음의 데이터를 삭제하거나 추가하거나 삭제하려고할때
해당 노드까지는 찾아가서 포인터(다음노드 주소)를 찾아야하면 결국은 crud 전부다 시간복잡도가 o(n)일 것 같다고 생각이 드는데 어떻게 이해를 하면 될까요?
Answer 1
0
안녕하세요, 인프런 AI 인턴입니다. alopp님.
링크드 리스트와 관련된 질문에 대해 도움을 드리겠습니다. 링크드 리스트에서의 시간 복잡도에 대해 이해할 때 고려해야 할 여러 요소가 있습니다. 기본적으로 링크드 리스트의 삽입과 삭제는 O(1)로 간주됩니다. 하지만 실제로 삽입 또는 삭제하려는 위치까지 찾아가는 과정 때문에 전체적으로 O(n)의 시간이 걸릴 수 있습니다.
즉, 특정 위치의 값을 삽입하거나 삭제하려면 그 위치까지 찾아가야 하기 때문에 탐색의 시간 복잡도가 O(n)입니다. 그러나 탐색이 완료된 이후의 삽입 또는 삭제는 노드의 포인터만 바꾸면 되므로, 이 자체의 연산은 O(1)입니다.
이미 비슷한 질문이 서로 다른 시점에 있었으니 아래의 URL들을 참고하시길 추천드립니다:
- Linked list의 장점 - 링크드 리스트의 탐색 및 삽입 삭제의 시간 복잡도에 대해 설명한 답변
- Linked List 시간 복잡도 - 실제 구현 시 발생하는 시간 복잡도와 이론상의 차이에 대한 답변
위 링크들을 통해, 링크드 리스트의 시간 복잡도가 어떻게 이해되어야 하는지 더 깊이 있는 설명을 볼 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
노션 접근이 안됩니다 ㅠㅠ
0
114
2
노션 공유 부탁드립니다.
0
55
2
노션 공유가 안됩니다!
0
150
2
프로세스가 많아질수록 segment table도 많아지는 건가요?
1
68
2
노션 공유가 사라졌습니다.
0
160
2
post 요청
0
52
1
http
0
59
1
mutex, semaphore와 deadllock
0
94
3
실행중인 프로세스는 메모리를 연속적으로? 아니면 불연속적으로 사용하나요?
0
70
1
노션 공유 요청 드립니다.
0
121
1
노션 공유 요청드립니다.
0
83
1
Dynamic Array와 Linked List의 시간복잡도에 대해서..
0
111
1
노션
0
107
1
질문이있습니다 선생님!
0
95
1
질문이있습니다 선생님!
0
88
1
질문이있습니다 선생님!
0
160
2
질문이있습니다 선생님!
0
148
2
질문이 있습니다 선생님!
1
195
2
질문이 있습니다 선생님!
0
119
1
질문이있습니다 선생님!
0
83
1
질문이 있습니다 선생님!
0
105
1
질문이 있습니다 선생님!
0
86
1
물리적 메모리에 연속적으로 저장하지 않는 이유
0
128
1
노션 공유부탁 드립니다.
0
124
1