빅 오 표현법 살표보기

빅 오 표현법은 알고리즘의 성능이나 복잡도를 설명하는 데 일반적으로 사용하는 방법이다. 빅 오 표현법은 입력 값이 바뀌었을 때 알고리즘의 선능이 어떻게 바뀌었는지를 알려준다.

예를 들어 가장 나쁜 성능을 가진 알고리즘을 표현하는 O(n²)는 입력 값이 2배가 되면 실행되는 시간은 4배로 늘어난다. 대부분의 경우 알고리즘이 원하는 정확한 의도를 표현한다고 하더라도 O(n²0>는 그다지 효율적인 방법이 아니다.

알고리즘을 작성할 때는 항상 해당 알고리즘의 빅 오 표현법이 어떻게 될지 생각해보는게 좋다. 빅 오 표현법은 n은 충분히 큰 값을 의미한다. n이 작을 때는 실행 시간이나 저장 공간의 낭비를 크게 신경 쓸 필요가 없다. 하지만 해당 알고리즘에서 사용하는 입력 값이 당장은 작더라도 시간이 지나면 엄청나게 큰 입력값도 처리할 수 있게 된다는 걸 기억하자.

알고리즘은 보통 최신^best-case, 최악^worst-case, 평균^average-case이라는 세 종류의 복잡성 중 하나에 속한다. 예상했겠지만 최선의 경우란 입력값이 주어졌을 때 알고리즘이 처리하는 횟수를 최대한 줄이는 것이다. 이러한 성능을 고려하는 것을 알고리즘의 시간 복잡성이라고 한다. 이와는 반대로 알고리즘이 수행될 때 얼마나 많은 저장 공간이 필요한가를 의미하는 공간 복잡성이라는 개념도 있다.

시간 복잡도와 공간 복잡도 사이에는 상반되는 관계가 있을 때가 많다. 처리 속도가 가장 빠른 알고리즘은 생각한 것보다 많은 저장 공간을 사용할 것이고 단 하나의 메모리 공간만 사용하는 알고리즘은 많은 공간을 사용하는 알고리즘보다 처리 속도가 많이 느릴 것이다.

따라서 알고리즘을 작성할 때는 시간/공간 복잡성을 함께 고려해야 한다. 요즘에는 메모리 가격이 많이 저렴해서 컴퓨터 대부분에 충분한 메모리가 탑재되어 있지만 여려분이 작성한 알고리즘이 정확히 어떻게 작동하는지 이해하는 건 중요하다.