[Algorithm - Big O Notation] 빅오 공식 소개 (3/4)

빅오에 대한 공식 소개

Big O Definition
We say that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases.²²²

Big O Notation is a way to formalize fuzzy counting. It Allows us to talk formally about how the runtime of an algorithm grows as the inputs grow.

 

빅오는 대략적으로 숫자를 세는 것에 붙인 공식적인 표현이다. 입력된 내용이 늘어날 수록 알고리즘의 실행 시간이 어떻게 변하는지 설명하는 공식적인 방식이다. 빅오는 어떤 함수의 입력 값이 늘어나는 것과 함수 실행 시간이 변하는 관계를 의미한다. 부차적인 것을 제외하고 오로지 전반적인 추세에 주목하는 것이다. 우리는 두번째 코드에서 n이 늘어남에 따라 실행되는 시간에 아무런 영향이 없다는 것을 확인했다. 하지만, 첫번째 코드의 경우 n의 값이 증가함에 따라 거의 1:1 비율로 선형으로 늘어났다. 

 

• f(n) could be linear (f(n) = n) // n의 값이 커질수록 실행 시간도 같이 선현을 의미한다.  
• f(n) could be quadratic (f(n) = n²) // n이 커질수록 n의 값이 제곱으로 늘어난다. 
• f(n) could be constant (f(n) =1) // n이 커져도 실행 시간에 영향을 주지 않는 상수이다. 
• f(n) could be something entirely different! // 

참고로 상기의 'f'는 함수를 뜻하고 '=' 뒤에 나오는 n은 출력 값이다. 즉, 입력과 실행 시간의 관계를 뜻하는 것이다.

 

코드에 따른 빅오 표기법

 

 

상기 코드는 빅오 표기법으로 'O(1)'으로 표현된다. O가 있고 가로안에 1, n, n², n log n 등을 쓸 수 있다. 

 

 

O(n) 코드

 

상기 코드에서 for문이 2개 존재하여 2n이라고 생각할 수 있지만 빅오에서는 그걸 신경쓰지 않는다. 큰 그림만 신경쓰기 때문에 이름도 빅오이다. 

 

O(n) 그래프

 

실제 그래프를 살펴보아도 O(n)과 크게 다를 것이 없다. 

 

O(n²) 코드

 

하지만 중첩 for을 사용하게 된다면 n²이 된다. 이 경우 n이 커질수록 실행 시간이 n제곱의 값으로 늘어나기 때문이다. 

 

O(n²) 그래프

 

그래프를 보면 n의 값과 시간이 비례해서 늘어나는 선형이 아니다. n 제곱의 값과 비례한다. n 곱하기 n만큼 늘어난다.  

 

 

출처

Udemy 사이트 Colt Steele의 알고리즘 강의 - https://www.udemy.com/course/best-javascript-data-structures/