C# - Big-O 표기법

Big-O표기법

알고리즘의 효율성을 분석하고 측정하기 위해 사용된다.

알고리즘의 성능을 분석 할때, 입력 데이터의 크기가 증가함에 따라 알고리즘의 연산량이 어떻게 증가하는지가 중요하다.

 

BIG-O표기법 1단계 : 대략적인 계산

수행되는 연산의 개수를 대략적으로 판단한다.

연산이 1개이면 1로 표기

반복문이 한개이고 연산이 1개이면 N + 1 표기

반복문이 두개이고 연산이 1개이면 N² + 1 표기

 

BIG-O표기법 2단계 : 대장만 남긴다

1)영향령이 가장 큰 대표 항목만 남기고 삭제한다.

예를 들어 2N² + 3N + 1이라면 2N²만 남기고 다 삭제한다.

2)상수 무시(2N² -> N²)

상수 값은 데이터의 크기가 무한히 커질 때 영향력이 작아지기 때문에 표기법에서 무시한다.

 

위에서 설명한거와 같이 Big-O표기법은

데이터가 크기가 늘어남에따라 연산량이 얼마나 증가하는지를 알려준다.

우측으로 갈수록 데이터가 많아지고 위로 갈수록 알고리즘 실행시간이 오래 걸린다.

 

출처 : https://medium.com/dataseries/how-to-calculate-time-complexity-with-big-o-notation-9afe33aa4c46

 

Big-O표기법에서 logN는 밑이 2인 로그 함수  log₂N 이다.