[BigO표기법이란]

 

알고리즘의 수행 시간을 표현 하는 방법은 상한을 나타내는 빅오(Big-O), 평균을 나타내는 빅오메가(big-Ω), 하한을 나태나는 빅세타(big-Θ)가 있는데 그중 우리는 빅오(Big-O) 를 사용한다.

 

 

Big-O는 증가율을 나태기 때문에 데이터의 입력이 충분이 큰 것으로 가정하고 사소한 부분들을 무시합니다.

따라서, 상수항이나 영향력이 없는 항은 무시하고 수행되는 연산(곱셈,덧셈 등)의 수를  계산하여 수행 시간을 나타낸다. 

 

 

BigO표기법은 기본적으로 최악의 경우의 복잡도 를 기준으로 측정한다.

 

해당 코드를 살펴 보자

for(int i=0; i<n;i++){
cout<<i <<'\n';
}

해당 코드는 최악의 경우 0에서 부터 n까지 연산을 수행한다. 따라서 해당 시간 복잡도는 O(n)이다.