[알고리즘] 시간 복잡도 Big-O

시간 복잡도란?

입력데이터가 n개 있을 떄, 최악의 경우의 연산 횟수를 n의 함수로 나타낸 것.

 

왜 입력데이터가 n개일 때인가?

알고리즘 A, B가 있을 때 두 가지 상황을 가정하자.

1. 입력 데이터가 다른 상황

A는 3초가 소요되는 알고리즘이고, B는 7초가 소요되는 알고리즘이다.

하지만 그렇다고 A가 더 빠른 알고리즘이라고 할 수 없다. 두 알고리즘에 대한 입력 값이 서로 다를 수 있기 때문이다.

 

2. 입력 데이터가 같아도 상황에 따라 다를 수 있다.

예를 들어, 10개의 데이터에 한해서는 A가 B보다 빠를 수 있지만, 10000개의 데이터에 한해서는 B가 더 빠를 수 있다.

 

결론: 그렇기 때문에 입력 데이터가 n개 일때, 최악의 경우의 연산 횟수를 n의 함수로 나타낸 것이 시간 복잡도 Big-O로 정하게 되었다.

 

Big-O 표기법 구하기

시간 복잡도 f(n)을 구했다면, 최고 차항의 변수 부분만 남겨야 시간복잡도가 된다.
예를 들어,
f(n) = O(3n2 + 4n)이 있다면, 최고 차항 변수인 n2만 남기면 된다.