[CS] 빅오 표기법

빅오 표기법이란?

알고리즘의 효율성을 예측하는 척도이다

 

ex) O(N), O(1), O(N^2), O(log n)

 

빅오 표기법으로 시간복잡도와 공간복자도를 표현할 수 있다

 

시간복잡도 : 시간에 관련된 효율성

 

공간복잡도 : 메모리에 관련된 효율성

 

기술이 발전하면서 공간복잡도는 고려하지 않고 시간복잡도를 고려한다

 

O(1)

입력값의 크기에 상관 없이 일정한 시간 소요

System.out.println(a);

 

O(log n)

입력값의 크기에 절반씩 감소하는 검색량

ex) Binary Search

13부터 42까지 오름차순으로 되어있을때

찾고자 하는 숫자를 구하기 위해 전체에서 절반의 숫자를 기준으로 계속 찾아내는 방법

 

이렇게 되면 8개를 3번만 비교하는 것이다

log 8 = 3

 

O(n log n)

입력값의 크기 만큼을 반으로 나누고 그 개 수 만큼 비교

ex) Merge Sort, Quick Sort, Heap Sort

분할정복 데이터를 계속 반으로 나눈다 1개가 남을 때 까지

그리고는 두개를 비교하고 합치는걸 반복한다

 

반으로 계속 나눌 때 log n

합병할 때 n 만큼 비교

결과적으로 O(n log n) 소요

 

O(N^2)

입력값의 크기에 따라 소요되는 시간이 제곱으로 증가

ex) Bubble Sort, Insertion Sort, Selection Sort

보통 이중 for문을 예시로 들 수 있다

 

O(2^n)

2번씩 입력값의 크기만큼 증가

ex) 피보나치 수열

보통 재귀함수를 예시로 들 수 있다

코딩테스트에서 메모이제이션 을 이용해 풀어야한다

 

O( 1) < O( log n) < O( n) < O( n* log n ) < O( n²) < O( n³)  < O( 2n ) < O( n! )