빅오

(자료구조 강의) Chapter 03 - 알고리즘 성능 분석

첫 번째 강의에서 순차 탐색 알고리즘과 이진 탐색 알고리즘의 성능을 비교하기 위해 데이터 1,000,000개를 가지고 테스트 했습니다. 데이터를 탐색하는데 걸리는 시간이 바로 나와서 확인하기 편했지만 모든 코드에 테스트 코드를 붙여서 테스트를 하려니 번거롭습니다. 또한 다음과 같은 의문이 들어 정확한 비교, 분석이라고 하기 애매합니다. ❝ 데이터가 1,000,000개가 아니라 10,000,000개 일 때는 얼마나 차이가 나요? ❞ ❝ 탐색 데이터가 배열 첫 번째에 있으면 이진 탐색보다 선형 탐색이 더 빠른 거 아닌가요? ❞ 알고리즘을 정확하게 비교하는 방법 우리는 알고리즘을 비교하고 분석하는 방법 중 하나인 빅-오 표기법을 알아볼겁니다. 다른 방법은 빅-오메가, 빅-세타가 있는데 다음과 같은 특징을 가집..