다음 탐색 알고리즘에 대한 설명으로 옳지 않은 것은?int a_sear… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 21년 1회차
다음 탐색 알고리즘에 대한 설명으로 옳지 않은 것은?int a_search(int list[], int key, int n) {
int i;
for(i=0; i<n; i++)
if(list[i]==key) return i;
return -1;
}
1
탐색에 성공하면 키 값의 인덱스를 반환한다.
2
최선의 경우, 시간 복잡도는 빅오 표기법으로 O(1)이다.
3
최악의 경우, 시간 복잡도는 빅오 표기법으로 O(n)이다.
4
평균적인 경우, 시간 복잡도는 빅오 표기법으로 O((n＋1)/2)이다.
해설
평균 시간 복잡도를 O((n+1)/2)로 적은 설명이 옳지 않다. 빅오 표기법은 상수 계수를 버리므로 평균의 경우도 O(n)으로 써야 한다.
순차 탐색의 평균 비교 횟수가 (n+1)/2회인 것은 맞지만, 점근 표기로는 n에 비례할 뿐이다.
- 일치하는 원소를 만나면 return i로 그 인덱스를 반환하므로, 성공 시 인덱스를 반환한다는 설명은 옳다.
- 첫 원소가 key이면 비교 1회로 끝나므로 최선의 경우 O(1)은 옳다.
- key가 맨 끝에 있거나 없으면 n회 비교하므로 최악의 경우 O(n)은 옳다.
오류나 개정된 내용이 보이면 알려주세요