태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.

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ⁿ)으로 치솟을 수도 있습니다.(일반적인 함수일 때는 이런 경우를 생각하기 어렵지만, 컴퓨터에서는 간혹 일어날 수 있습니다) 인 함수가 평균적으로 "대충 이정도 시간이 걸릴꺼야!"보다 "절대로 이 시간 이상은 넘지 않을거야!"라고 말하는 것이 신뢰도가 높습니다.

 





  1. 친절한공대생 2017.08.17 07:41 신고

    글 잘 읽었습니다! 그런데 궁금한 점이 있는데요. "6. 현실에서 가장 많이 쓰이는 것은?"에서 세타 n인 함수가 어떻게 빅 오 2^n일 수 있죠? worst-case와 average-case, best-case에 대해서 말씀하고 계신거라면 약간 미흡한 표현 아닐까요? worst-case(혹은 average-case나 best-case)에서 세타 n인 함수는 tightest upper bound도 O(n)이니까요.

  2. ㅇㅇ 2019.06.15 19:35

    빅 오, 빅 오메가, 빅 세타는 최악, 최선, 평균 케이스에 해당하는 복잡도를 의미하는 바가 아닙니다.
    알고리즘의 최악, 최선, 평균 케이스에 각각 빅 오, 빅 오메가, 빅 세타를 계산할 수 있습니다.
    빅 오는 해당 케이스에 해당 알고리즘의 복잡도의 상한,
    빅 오메가는 해당 케이스에 해당 알고리즘의 복잡도의 하한,
    빅 세타는 해당 케이스에 해당 알고리즘의 정확한 복잡도를 나타냅니다.
    예를들어 퀵 소트의 평균 케이스는 빅 세타(NlogN)이고 최악 케이스는 빅 세타(N^2)입니다.
    만약 평균 케이스에 빅 세타(NlogN)을 증명하지 못해도 빅 오(N^2)에 속하거나 증명할 수도 있고 빅 오메가(1)에 속함도 증명할 수 있죠.
    아마 빅 오 표기법은 단순히 세타보다 컴퓨터로 입력하기 쉬워서가 아닐까 싶네요.

+ Recent posts