(섹션 3 퀴즈 관련) - 배열과 링크드 리스트 시간 복잡도 질문
섹션 3 퀴즈에서 헷갈리는 부분이 생겨서 질문드립니다.
문제의 일부는 아래와 같습니다. (정답은 B)
1. 배열과 링크드 리스트의 주요 성능 차이점 중 하나는 무엇일까요?
A 배열은 요소 탐색 시 O(1)이 걸리지만, 링크드 리스트는 O(N)이 걸립니다.
B 링크드 리스트는 중간에 요소를 삽입/삭제 시 O(1)이 걸리지만, 배열은 O(N)이 걸립니다.
제가 헷갈리는 부분
A도 정답이 될 수 있지 않을까요? (A를 선택한 경우 오답으로 처리됨)
수업과 수업 자료를 통해 이렇게 이해 했습니다.
"특정 원소 조회시 배열은 O(1), 링크드 리스트는 O(N)의 시간 복잡도를 가진다"
요소 탐색과 요소 조회는 다른 개념일까요?
답변 1
0
안녕하세요 코딩코딩님!
해당 퀴즈는 AI 가 생성하는 값이라 제가 작성한 자료는 아닙니다!
따라서 이 점을 참고해주시길 바랍니다 ㅎㅎㅎ
조회는 말씀해주신대로 "특정 원소 조회시 배열은 O(1), 링크드 리스트는 O(N)의 시간 복잡도를 가진다"
가 맞습니다!
아마 퀴즈의 탐색이라는 단어를 특정 원소를 찾는 과정을 의미한 것 같습니다.
그래서 배열에서 특정 원소를 "탐색"하기 위해서는 모든 원소를 찾아야 하기 떄문에 O(N) 이 걸리기 떄문에 오답으로 인식된 것 같습니다.
그런데, 사실 저 탐색이라는 단어 자체가 매우 모호한 것 같아요. 그래서 좋지 않은 퀴즈였고, 루꾸님이 해당 부분에 대해 이의를 제기한게 매우 맞는 방향성이라고 생각이 듭니다! 좋은 질문 감사합니다 ㅎ.ㅎ
링크드 리스트 중간 삽입삭제 시간복잡도 질문
0
37
2
재귀함수 종료조건
0
34
2
백준 사이트 준비중이라 문제를 볼 수 가 없어요
0
57
2
해당 차수 영상이 짤려 나갑니다
0
54
2
1-11 소수 나열하기 (에라토스테네스의 체)
0
70
1
수강평 이벤트
0
94
2
코딩테스트 처음인데 이런 공부방법이어도 괜찮을까요
0
185
2
3-3 정렬-2 선택정렬 로직
0
82
2
링크드 리스트 끝에서 k번째 값 출력하기
0
77
2
LinkedList 과제 Fast, slow 포인터
0
76
2
투포인터 시간복잡도
0
90
2
수강평 작성 후 자료
0
82
2
수업교재 링크 오류
2
147
2
프로그래머스에서 제출 후 채점시 틀림ㅠ
0
195
2
1-10 알고리즘 더 풀어보기(2) 질문 있습니다
0
109
2
문제 풀이 방식 관련 질문입니다!
0
124
2
1-5 알고리즘과 친해지기 (2) - 최빈값찾기 질문 있습니다
0
127
2
수업자료 pdf 받고싶습니다
0
140
2
강의 자료 오류 수정
0
101
1
2-10 더하거나 빼거나 관련 질문입니다
0
89
2
3-8 해쉬 -2
0
69
2
Linked List Element Delete Explanation Problem
0
96
2
강의3-4 스택 탑 문제
0
105
2
코드스니펫 입출력 케이스에 오류가 있는것 같아요
0
132
3