2번. 배열 리스트와 연결 리스트

미분류 · 0pt

오름차순으로 정렬된 n개의 원소 중 특정 값 x를 찾아 삭제하려 한다. 배열 리스트: 이진 탐색으로 x를 찾은 뒤 뒤쪽 원소들을 앞으로 이동한다. 단일 연결 리스트: 더미 헤드부터 순차 탐색하면서 prev와 curr을 함께 유지하고, x를 찾으면 링크를 변경하여 삭제한다. 두 방식의 최악 시간 복잡도를 올바르게 나타낸 것은?