점근 표기법

Jace·2023년 1월 8일
0

점근 표기법 (Asymptotic Notation)

어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 방법.
쉽게 이해하자면 시간 복자도를 근사치로 표현한 것.

예를 들어 A 함수와 B 함수의 비교하여 어떤 성능이 더 좋은지 결정하는 것.

대표적으로 다섯 가지 표기법이 있다.

  • 대문자 O 표기법
  • 소문자 o 표기법
  • 대문자 오메가(Ω) 표기법
  • 소문자 오메가(ω) 표기법
  • 대문자 세타(Θ) 표기법

대문자 O 표기법

컴퓨터 공학에서 알고리즘의 복잡도 또는 성능을 표현하기 위해 사용.
특히 최악의 경우를 표현하며, 알고리즘의 실행 시간이나 사용 메모리 공간을 표현하기도 한다.

소문자 o 표기법

빅 오 표기법 보다 좀 더 여유있는 상한을 표현할 때 사용.
알고리즘의 복잡도 또는 성능을 표기할 때는 자주 쓰이지 않는다.

대문자 오메가(Ω) 표기법

빅 오 표기법과 마찬가지로 알고리즘의 복잡도 또는 성능을 표기할 때 사용.
하지만 빅 오메가 표기법은 최고의 경우를 표현한다.

소문자 오메가(ω) 표기법

빅 오메가 표기법보다 좀 더 여유있는 상한을 표현할 때 사용

대문자 세타(Θ) 표기법

평균의 경우를 나타내는 표기법.
빅 오 표기법과 빅 오메가 표기법의 교집합 -> 아무리 좋아지거나 아무리 나빠지더라도 세타 범위 안에 있다.

참고자료

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=nsj6646&logNo=221511635919

https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation

https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95

신은 용기있는자를 결코 버리지 않는다 -켄러

profile
오늘한줄.

0개의 댓글