1-3 빅오표현법 Big - O notation

알고리즘 성능 분석할 때, 빅오표현법(Big-O notation)이라는 것을 사용합니다.

 

모든 개발자들이 코드를 짤 때, 코드가 빨리 실행이 되는 것을 원하겠죠? 빠르게 실행되는 알고리즘을 짜기 위한 시간 측정 방법입니다.

 

빅오에 대해 처음 들어보시는 분들은 이해가 잘 안되실 수도 있으니 아래의 예시를 들어 놨습니다.

 

 

위의 코드를 보면 big_o1 이라는 애를 실행하면, 연산이 딱 1번 됩니다. 때문에 이 아이의 시간복잡도 big-0는 O(1) 입니다.

 

아래 코드도 또 보겠습니다.

 

위의 big_oN이라는 함수는 arr라는 것의 크기 만큼 실행되기 때문에 얘의 big-o는 O(N)입니다.

 

또 여기에 중첩반복문을 통해서 O(N * N) 즉 O(N^2) 을 아래와 같이 만들 수도 있습니다.

 

그리고 여러가지 정렬을 실행할 때 O(NlogN)이라는 것도 나옵니다. 아래의 트리(tree) 형태의 데이터를 다룰 때

(이 부분은 뒤에가서 자세히 다루겠습니다.)

 

빅오를 아래와 같이 정렬해봤습니다.

 

O(1) < O(log N) < O(N) < O(NlogN) < O(N^2) < O(2^n) 

 

왼쪽애 있는 애 일 수록 빠르고, 오른쪽에 있는 애 일 수록 느립니다.

 

다음시간부터 하나씩 정렬을 해 가면서, 알아보겠습니다.