[알고리즘] 시간복잡도

알고리즘의 효율성

• 길이(개수)가 N인 데이터에 대한 연산의 횟수

점근 표기법

case에 따라 분류

• best case
  첫번째에 target값 존재 => 1번째만에 target값 찾음
• worst case
  마지막에 target값 존재 혹은 target값 없음 => N번째에 target값 찾음 or N번 다 돌고 못찾음

lower bound, 점근표기법 Ω(1) Ω(N) = Big-Omega 표기법
알고리즘의 효율성을 하한선을 기준으로 설명

• 함수 실행시간은 아무리 빨라도 (상수) 시간 이상이다

upper bound, 점근표기법 O(N) O(1) = Big-O 표기법
알고리즘의 효율성을 상한선을 기준으로 설명

• 함수 실행시간은 아무리 오래걸려도 N에 비례하는 정도 이하다

tight bound, 점근표기법 Θ(N) Θ(N) = Big-theta 표기법
lower bound 와 upper bound가 같을 때 Θ를 사용해서 표현할 수 있다.

이진 탐색 Binary Search의 시간복잡도

이진 탐색

• 정렬 되어 있는 배열에서 특정한 값을 찾아내는 알고리즘

• 배열의 중간값과 target값을 비교하여 탐색한다.
• target값이 중간값보다 작을 경우 왼쪽, 클 경우 오른쪽을 탐색
• 루프를 돌며 중간값과 target값을 비교해가며 target값을 찾는다.

이진 탐색의 시간복잡도

결국 이진 탐색은 중간 값을 찾아 자르고 자르고를 반복하기 때문에,
target값을 찾을 때까지(배열의 길이가 1이 될 때 까지) N 1/2를 반복한다.
함수를 k번 실행했을 때 N = 1이 된다고 했을 때,
N(1/2)^k = 1로 표현할 수 있다.

N/2^k = 1
N = 2^k
#양 쪽에 log2를 붙이면
log2N = k

이진 탐색의 시간복잡도는 log2N이고,
이 때 upper bound를 점근표기법으로 표기한 것이 O(logN)이다.

시간복잡도의 비교

O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(2^N) < O(N!)