[자료구조] 1.2 알고리즘의 성능분석 방법 (6)

알고리즘의 성능분석 방법 (6)

순차 탐색 알고리즘과 이진 탐색 알고리즘 비교

순차 탐색 알고리즘

• 최악의 경우 시간 복잡도 : T(n) = n
• 순차 탐색 알고리즘의 빅-오표기법 : O(n)

이진 탐색 알고리즘

• 최악의 경우 시간 복잡도 : T(n) = log_{2}n + 1
• 이진 탐색 알고리즘의 빅-오표기법 : O(log n)

n의 값에 따른 순차 탐색과 이진 탐색의 연산 횟수

비교

• 빅오표기법으로 시간복잡도를 봤을 때 이진 탐색 알고리즘 O(log n) 가 순차 탐색 알고리즘 O(n) 보다 효율적이다.
• 이진 탐색 알고리즘의 성능이 우수하지만 이진 탐색 알고리즘의 경우 정렬된 데이터에서만 사용이 가능하다

참고

• 윤성우의 열혈 자료구조
  
• 윤성우의 열혈 자료구조 강의