알고리즘 표기법

핵심 단어

• Big O
• Big Ω(Omega)
• Big θ(Theta)

Big O

• 컴퓨터 과학에서 “대략”을 나타내는 공식적인 개념.
• 최악의 경우(실행 시간의 상한 = 제일 느린 경우)에 대한 시간 복잡도를 나타내는 표현이다.

표기	알고리즘 예시
O(n^k)	-
O(2&n)	-
O(n^3)	-
O(n^2)	bubble sort(거품 정렬),
	insertion sort(삽입 정렬),
	selection sort(선택 정렬)
O(n log n)	merge sort(병합/합병 정렬),
	Quick sort(퀵 정렬)
O(n)	linear search(선형 탐색)
O(log n)	binary search(이진 탐색)
O(1)	-

Big Ω(Omega)

• Big-O와 반대되는 개념으로 최선의 경우(실행 시간의 하한 = 제일 빠른 경우)에 대한 시간 복잡도를 나타내는 표현이다.

표기	알고리즘 예시
Ω(n^2)	selection sort(선택 정렬)
Ω(n log n)	merge sort(병합/합병 정렬)
Ω(n)	insertion sort(삽입 정렬),
	bubble sort(거품 정렬)
Ω(log n)	-
Ω(1)	linear search(선형 탐색),
	binary search(이진 탐색)

Big θ(Theta)

• 알고리즘의 상한선과 하한선이 같을 때, 즉 평균에 대한 시간 복잡도를 나타내는 표현이다.

표기	알고리즘 예시
θ(n^2)	selection sort(선택 정렬)
θ(n log n)	merge sort(병합/합병 정렬)
θ(n)	-
θ(log n)	-
θ(1)	-

Big O, Big Ω(Omega), Big θ(Theta) 표기법 예시

• 탐색, 정렬, 자료구조, 메서드 별 예시

  • 탐색 알고리즘

    

  • 정렬 알고리즘

    
    

  • 자료 구조, 메서드

    

참고