공간복잡도와 빅오 표기법
조회수 677회
공부를 하던 중, " ~~~ using O(n) storage"라는 표현을 발견했습니다. 저는 이게 빅오에 storage니까 공간복잡도와 관련되지 않았을까?? 생각하게 되었고, 공간 복잡도에 대해 조사를 해봤죠.
https://m.blog.naver.com/demonic3540/221229805234 여기 글에서 공간복잡도에 대해 잘 설명하고 있지만, "공간복잡도가 n+1이다."라고 말하지, "공간복잡도가 O(n)이다."라고 표현하지는 않았더군요.
Q : 과연 이렇게 공간복잡도도 빅오 표기법으로 표현하는 경우가 있을까요??
(물론 이 의문을 처음 떠올리게 한 using O(n) storage는 뭔가 n개 입력에 대해 선형적인 메모리를 사용하게 된다는 말로 이해되기는 합니다.)
-
-
(•́ ✖ •̀)
알 수 없는 사용자 - 〉
1 답변
-
notation(표기법)은 단순히 표기법일 뿐,
시간/공간 복잡도와 독립적으로 생각한다고 보면...
시간 복잡도에서는 이중 반복문처럼 최대 n2 걸리는 것을 O(n2) 처럼 표기하듯,
특정 알고리즘의 성능적인 상한선이란 의미로 본다면 가능할 것 같습니다.
공간 복잡도에서는
특정 단위 메모리가 1개만 필요할 수도 있고
혹은 n + 1 만큼 필요할 수도 있지만
최대로 n * m개는 넘어가지 않을 것이란 의미로 O(n*m) 처럼 쓸 수 있지 않을까요?
https://www.quora.com/How-do-we-calculate-space-complexity
여기 답글들 중에 보시면, 표기법 자체는 증가 양상을 표현하는 방법일 뿐이기 때문에 실제로도 Big O 표기법으로도 표현한다고 합니다.
댓글 입력