시간복잡도

빅 표기볍

빅 표기법(Big Notation) 에는 3개의 표기법이 있습니다.

• Big-O(빅-오) : 시간복잡도가 최악의 경우 일 때 표기
• Big-Ω(빅-오메가): 시간복잡도가 최선의 경우 일 때 표기
• Big-θ(빅-세타) : 최선의 경우와 최악의 경우가 같을 때 표기

우리가 이 친구들을 배우는 이유는 보통 사용하는 자료구조 또는 알고리즘의 성능을 표시하기 위해서 입니다. 보통 최선의 경우는 잘 쓰이지 않고(→ 대부분 바로 찾기 때문에), 최악의 경우를 많이 활용하므로 Big-O 표기가 자주 사용됩니다.

시간복잡도에서 빅오(Big-O) 표기법 구분 예시

• O(n) : 배열에서 원하는 값을 찾기 위해 처음부 끝 까지 순서대로 탐색하는 경우
• O(log n) : 배열에서 원하는 값을 찾기 위해 탐색의 대상을 절반씩 줄여나가는 경우
• O(1): 배열에서 원하는 값을 바로 찾는 경우
• O(n^2): O(n)을 수행하는 연산이 2번 중첩되어 실행되는 경우 ex. 2중 for문
• O(n^3): O(n)을 수행하는 연산이 3번 중첩되어 실행되는 경우 ex. 3중 for문

Big-O 가 자주 사용되는 이유

보통 컴퓨터로 작업할 때 최선의 경우 보다는 최악의 경우에 작업량이 엄청나게 늘어나는 경우가 있습니다. 따라서 이 상황을 방지하기 위해 항상 최악의 경우를 잘 고려해주어야 합니다.