Big-O 표기법

Big-O 표기법

 - 알고리즘의 효율성을 나타내는 표기법
 - 입력의 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는지 설명
 - Big-O 표기법은 알고리즘의 최악의 경우 성능을 나타냄

 

예시

 - O(1) : 상수 시간, 입력의 크기에 상관 없이 항상 일정한 시간이 걸림
 - O(n) : 선형 시간, 입력의 크기에 비례하여 시간이 걸림
 - O(n^2) : 이차 시간, 입력의 크기의 제곱에 비례하여 시간이 걸림
 - O(log n) : 로그 시간, 입력의 크기의 로그에 비례하여 시간이 걸림

 

계산방법

1. 상수 버리기 : 상수 항목이나 낮은 차수의 항목은 중요하지 않으므로 버림
 ex) O(2n) -> O(n), O(3n^2) -> O(n^2)
2. 최고 차수 항목만 남기기 : 가장 빠르게 증가하는 항목에 초점을 맞춤 
 ex) O(n^2 + n) -> O(n^2)
3. 다항식의 경우 최고 차수 항목만 고려 : 가장 빠르게 증가하는 항목에 초점을 맞춤
 ex) O(3n^3 + 5n^2 + 2n + 7) -> O(n^3)
4. 연산자 상수 무시
 ex) O(3n^2 + 4n + 2) -> O(n^2)