Algorithm 이진 탐색

선형 탐색

 

선형성

1. 선형성에 있다 = 그래프에서 직선으로 나타낼 수 있다
2. 그래프의 직선을 축 2개의 숫자 쌍으로 나타낼 수 있다

 

선형 알고리즘 (liner algorithm)

1. 요소 개수 증가에 정비례하게 실행 시간이 증가. 시간 복잡도 O(n)

 

선형 탐색

1. 결과를 알기 위해 배열의 모든 요소를 살펴봐야한다.
2. 배열의 크기가 커질수록 오래 걸린다. 

 

 

---

로그

지수

 

 

1. a : 밑 (base) ( a > 1 )
2. x : 지수 (exponent) or 거듭제곱 (power)

 

자연 로그

1. e : 밑, 오일러의 수
2. x : 지수
3. 반감기 계산, 경제 및 금융 등에 쓰인다.

 

로그

 

---

이진 탐색

작동 방식

1. 탐색하고자 하는 숫자와, 배열 중앙의 숫자를 비교한다. 
2. 배열 중앙의 숫자가 더 작으면 그 숫자부터 밑에 숫자를 다 제거한다.
3. 다시 탐색하고자 하는 숫자와, 남은 배열의 중앙 숫자를 비교한다.
4. 이를 반복하면 탐색하고자 하는 숫자의 인덱스를 알 수 있다.

이진탐색 (binary search)

1. 시간 복잡도 O(logn)
2. 배열이 정렬된 상태에서만 제대로 동작한다.
3. 규모가 커져도 탐색 시간이 별로 늘지 않는다.