인프런 커뮤니티 질문&답변
작성한 질문수
(섹션 3 퀴즈 관련) - 배열과 링크드 리스트 시간 복잡도 질문
해결된 질문
작성
·
48
0
섹션 3 퀴즈에서 헷갈리는 부분이 생겨서 질문드립니다.
문제의 일부는 아래와 같습니다. (
정답은 B)
1. 배열과 링크드 리스트의 주요 성능 차이점 중 하나는 무엇일까요?
A 배열은 요소 탐색 시 O(1)이 걸리지만, 링크드 리스트는 O(N)이 걸립니다.
B 링크드 리스트는 중간에 요소를 삽입/삭제 시 O(1)이 걸리지만, 배열은 O(N)이 걸립니다.제가 헷갈리는 부분
A도 정답이 될 수 있지 않을까요? (A를 선택한 경우 오답으로 처리됨)
수업과 수업 자료를 통해 이렇게 이해 했습니다.
"특정 원소 조회시 배열은 O(1), 링크드 리스트는 O(N)의 시간 복잡도를 가진다"
요소 탐색과요소 조회는 다른 개념일까요?
퀴즈
배열과 링크드 리스트의 주요 성능 차이점 중 하나는 무엇일까요?
배열은 요소 탐색 시 O(1)이 걸리지만, 링크드 리스트는 O(N)이 걸립니다.
링크드 리스트는 중간에 요소를 삽입/삭제 시 O(1)이 걸리지만, 배열은 O(N)이 걸립니다.
배열은 동적 크기 조절이 자유롭지만, 링크드 리스트는 고정 크기입니다.
링크드 리스트는 연속된 메모리 공간에 저장되지만, 배열은 비연속적입니다.
답변 1
1
안녕하세요 루꾸님!
해당 퀴즈는 AI 가 생성하는 값이라 제가 작성한 자료는 아닙니다!
따라서 이 점을 참고해주시길 바랍니다 ㅎㅎㅎ
조회는 말씀해주신대로 "특정 원소 조회시 배열은 O(1), 링크드 리스트는 O(N)의 시간 복잡도를 가진다"
가 맞습니다!
아마 퀴즈의 탐색이라는 단어를 특정 원소를 찾는 과정을 의미한 것 같습니다.
그래서 배열에서 특정 원소를 "탐색"하기 위해서는 모든 원소를 찾아야 하기 떄문에 O(N) 이 걸리기 떄문에 오답으로 인식된 것 같습니다.
그런데, 사실 저 탐색이라는 단어 자체가 매우 모호한 것 같아요. 그래서 좋지 않은 퀴즈였고, 루꾸님이 해당 부분에 대해 이의를 제기한게 매우 맞는 방향성이라고 생각이 듭니다! 좋은 질문 감사합니다 ㅎ.ㅎ