(섹션 3 퀴즈 관련) - 배열과 링크드 리스트 시간 복잡도 질문

Question

섹션 3 퀴즈 에서 헷갈리는 부분이 생겨서 질문드립니다. 문제의 일부는 아래와 같습니다. ( 정답은 B ) 1. 배열과 링크드 리스트의 주요 성능 차이점 중 하나는 무엇일까요? A 배열은 요소 탐색 시 O(1)이 걸리지만, 링크드 리스트는 O(N)이 걸립니다. B 링크드 리스트는 중간에 요소를 삽입/삭제 시 O(1)이 걸리지만, 배열은 O(N)이 걸립니다. 제가 헷갈리는 부분 A도 정답이 될 수 있지 않을까요? (A를 선택한 경우 오답으로 처리됨) 수업과 수업 자료를 통해 이렇게 이해 했습니다. "특정 원소 조회시 배열은 O(1), 링크드 리스트는 O(N)의 시간 복잡도를 가진다" 요소 탐색 과 요소 조회 는 다른 개념일까요?

딩코딩코 · Answer

안녕하세요 루꾸님! 해당 퀴즈는 AI 가 생성하는 값이라 제가 작성한 자료는 아닙니다! 따라서 이 점을 참고해주시길 바랍니다 ㅎㅎㅎ 조회는 말씀해주신대로 "특정 원소 조회시 배열은 O(1), 링크드 리스트는 O(N)의 시간 복잡도를 가진다" 가 맞습니다! 아마 퀴즈의 탐색이라는 단어를 특정 원소를 찾는 과정을 의미한 것 같습니다. 그래서 배열에서 특정 원소를 "탐색"하기 위해서는 모든 원소를 찾아야 하기 떄문에 O(N) 이 걸리기 떄문에 오답으로 인식된 것 같습니다. 그런데, 사실 저 탐색이라는 단어 자체가 매우 모호한 것 같아요. 그래서 좋지 않은 퀴즈였고, 루꾸님이 해당 부분에 대해 이의를 제기한게 매우 맞는 방향성이라고 생각이 듭니다! 좋은 질문 감사합니다 ㅎ.ㅎ