int search(const int a[], int n, int key)
{
int i = 0;
while(i < n) {
if(a[i] == key)
return i;
i++;
}
return -1;
}
O(1) : 데이터 수 n과는 무관하게 한 번만 실행하는 경우
int i = 0;
return i;
return -1;
O(n) : n에 비례하는 횟수만큼 실행하는 경우
while(i < n)
if(a[i] == key)
i++;
2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시함
int bin_search(const int a[], int n, int key)
{
int pl = 0;
int pr = n - 1;
int pc;
do {
pc = (pl + pr) / 2;
if (a[pc] == key)
return pc;
else if (a[pc] < key)
pl = pc + 1;
else
pr = pc - 1;
} while (pl <= pr);
return -1;
}
O(1)
int pl = 0;
int pr = n - 1;
return pc;
return -1;
O(log n)
그 외 나머지