C++ 알고리즘 - binary search, complexity

Complexity

:: 알고리즘 성능을 객관적으로 평가하는 기준

 

<요소>

1. Time complexity : 실행에 필요한 시간 평가한 것

2. Space complexity : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

---

‣ n에 비례하는 횟수만큼 실행하는 경우 : 복잡도 O(n)

 

‣ O(f(n))과 O(g(n))의 복잡도 계산 방법

       O(f(n)) + O(g(n)) = O(max(f(n), g(n))

 

‣ 전체 복잡도 = 차원이 가장 높은 복잡도를 선택

       선형 알고리즘 복잡도 = O(n)

ex) O(1)+O(n)+O(n)+O(1)+O(n)+O(1) = O(max(1,n,n,1,n,1) => O(n)

 

---

Q1) search func를 for문을 사용하여 수정

// 요소 개수가 n인 배열a에서 key와 일치하는 요소를 선형 검색
int search(int a[], int n, int key){
    int i=0;// 배열 순서
    a[n]=key; //보초 추가
    for(i=0;i<n;i++){
        if(a[i]==key)
            break;
    }
    return i==n ? -1 : i; //i==n 이면 찾은 값이 보초값이다 그래서 -1 return
}