1.개요
알고리즘을 시간적인 관점에서 보는 시간복잡도와 비슷하게, 알고리즘을 공간적인 관점에서 보는 공간복잡도에 대해서 알아보겠습니다.
2.빅-오(Big-Oh) 표기법
대개 최악의 경우라고 하죠. 상한 점근이란 것은, 대부분의 경우, "너가 지금 설계한 알고리즘의 시간복잡도가 얼마쯤 되니?" 라고 하면 "O(n logn)정도 됨 ㅇㅇ" 라고 대답할정도로 빅오는 시간복잡도를 논할때 가장 보편적인 표기입니다. 다시한번 정의를 적어보죠.
3. 빅-오메가(Big-Omega) 표기법
빅 오메가는 빅 오와는 반대되는 개념입니다. 대개 최선의 경우라고 합니다. 빅오는 "너는 언젠가 내 안의 함수보다 작아지게 될거야"라고 의미하는 것이라면, 빅 오메가는 "너는 언젠가 내 안의 함수보다 커질꺼야" 정도로 해석됩니다. 정의는 이렇습니다.
위의 빅오 정의와 다른 점은, 부등호의 방향이 반대라는 것입니다.
예를 들어, n²+2n+1=Ω(n²), Ω(log n), Ω(n), Ω(1)이 됩니다.(오메가 안에 있는 함수들이 일정 숫자 이상이 되면 왼쪽의 식보다 항상 작아집니다)
또 하나 빅오메가를 쉽게 생각하는 방법은 이렇습니다.
왜냐하면, 위의 n이 일정 수 이상일때 f(n)은 g(n)보다 작습니다. 그렇다는 것은, n이 일정 수 이상일때 g(n)은 f(n)보다 크다는 것이죠. 이 것은 위의 빅오메가가 될수 있는 조건이 되기 때문에 위의 명제가 성립하는 것입니다.
4.세타(Theta) 표기법
빅 세타는 빅 오와 빅 오메가의 공통부분입니다. 최소와 최악의 중간인 평균적인 복잡도이죠.
빅 세타는 "너는 내안의 함수와 동등한 비율로 증가해" 라고 의미하는 것입니다.
n²+2n+1의 경우를 예로들면, 이 함수는 O(n²)과 Ω(n²)을 동시에 만족합니다. 그렇기 때문에 이 함수는 Θ(n²)이라고 할 수 있습니다. 반면에, O(n³)같은 경우는 Ω(n³)을 만족시키지 못하고, Ω(n*log n)은 O(n*log n)을 만족시키지 못합니다. 그러므로 저 함수들은 n²+2n+1을 세타 표기법으로 표기할 수 없습니다.
5.공간복잡도
공간복잡도는, 어떤 알고리즘이 있을때, 이 알고리즘을 수행해서 공간(그러니까 RAM이나 하드디스크의 메모리 같은 곳)이 얼마나 필요한가를 표기하는 것입니다. 공간복잡도도 빅오, 빅오메가, 빅세타로 표기할수 있으며, 시간복잡도와 다른 점은 단지 시간관점인가 공간관점인가 그것밖에 없습니다.
6.현실에서 가장 많이 쓰이는건?
아무래도 컴퓨터 프로그래밍쪽에서는 빅오 표기법이 널리 사용됩니다. 왜냐하면, 알고리즘의 평균적인 시간은 의미가 없는 경우가 많기 때문입니다. 극단적인 경우,Θ(n)인 함수가 투입되는 경우에 따라 O(2ⁿ)으로 치솟을 수도 있습니다.(일반적인 함수일 때는 이런 경우를 생각하기 어렵지만, 컴퓨터에서는 간혹 일어날 수 있습니다) 인 함수가 평균적으로 "대충 이정도 시간이 걸릴꺼야!"보다 "절대로 이 시간 이상은 넘지 않을거야!"라고 말하는 것이 신뢰도가 높습니다.
