Firebase의 Hosting, Functions, Firestore를 이용하여 웹상에 메모장을 만들기
2018-02-13
자바스크립트로 알아보는 알고리즘 #2 공간 복잡도, 빅오 표기법
2019-03-02
Explanation
이번엔 지난 글에 이어서 공간 복잡도와 빅오 표기법에 대해 알아보려 합니다.
이번 글도 역시 글 내용이 대부분 다른 블로그의 글을 읽으며 공부하고 정리한 내용이다보니,
참고한 글의 링크를 먼저 알려드릴게요.
1. https://qwe1qwe.tistory.com/880
2. https://cjh5414.github.io/big-o-notation/
3. https://madplay.github.io/post/time-complexity-space-complexity
4. https://wayhome25.github.io/cs/2017/04/20/cs-26-bigO/
5. https://vaert.tistory.com/117
6. https://ledgku.tistory.com/31
제가 공간 복잡도에 대한 이해가 부족하고, 블로그의 글들도 대부분 바로 빅오 표기법으로 알려주는 경우가 많아서 잘못된 부분이 많을 수 있습니다. 잘못된 부분은 댓글로 알려주시면 감사할 거 같아요…
추후에 공간 복잡도에 대해 확실히 공부를 해서 그때 다시 수정하도록 하겠습니다.
이전 글에서 살짝 이야기를 했었는데, 공간 복잡도는 알고리즘이 수행되는데 필요한 기억장치(메모리(RAM))의 크기를 이야기합니다.
우선 인터넷에서 찾아본 간단한 예를 살펴봅니다.
|
1 2 3 |
function sample(a, b, c) { return a + b + c * a; } |
위 예의 경우 a, b, c는 3개의 변수로 메모리상 1씩 3개해서 3을 차지하는 것처럼 보일 수 있지만, 외부에서 인자로 받아오고 함수는 바로 리턴하기 때문에 공간 복잡도는 0입니다.
빅오 표기법으로는 O(1) 이려나요..?
|
1 2 3 4 5 6 7 8 |
// arr = 배열, n = 정수 function sample(arr, n) { let s = 0; // 1 for(let i=0; i<n; i++) { // 2; s += arr[i]; // n } return s; } |
위 예에서는 우선 변수 s를 초기화하는 1, 그리고 i를 초기화하는 1, 그리고 for문을 끝내기 위한 n값 1, 끝으로 반복문에서 arr[i]의 n값을 해서 총 공간 복잡도는 n + 3 이됩니다. (그런데 여기서 for문을 끝내기 위한 n의 값 1이 아직 이해가 잘 되지 않네요…)
빅오 표기법으로는 O(n) 일 거 같아요.
|
1 2 3 4 5 6 7 8 |
// n = 정수 function sample(n) { let val = 1; for(let i=0; i<n; i++) { val = val * i; } return val; } |
위 예가 시간 복잡도와의 차이를 잘 느끼게 해주는 거 같아요. 아마도 val 이라는 변수를 초기화 하는데 1, 그리고 반복문에 사용된 변수 i에 1. 그래서 반복문이 몇번 반복되는 것과 상관 없이 공간 복잡도는 2가 되고 빅오 표기법으로는 O(1)이 될 거 같아요.
|
1 2 3 4 5 |
// n = 정수 function sample(n) { if(n < 0) return 0; return n + sample(n-1); } |
위 예의 경우에는 n의 개수만큼 sample 함수가 반복 실행되겠죠? n개수 만큼 콜 스택이 쌓이기 때문에 위 공간 복잡도를 빅오 표기법으로하면 O(n)이 됩니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// n = 정수 function sample(n) { let result = 0; for(let i=0; i<n; i++) { result = innerSample(i, i+1); } return resukt; } function innerSample(a, b) { return a + b; } |
위 예는 단순히 함수가 호출되는 수 만큼 공간을 차지하지 않는다는 걸 알려주는 예 인거 같아요. innerSample이라는 함수는 n번만큼 호출되지만 리턴값이 result라는 하나의 공간에 들어가기 때문에 공간 복잡도는 result, innerSample() 해서 2이고 빅오 표기법으로는 O(1)이 되는 것 같습니다.
몇가지 예를 찾아보았는데요, 어느 정도 알 것도 같으면서 잘 모르겠네요.
다음에 서점에 가서 책으로 한번 다시 살펴보는게 좋을 거 같아요.
지금 와서 생각해보니 빅오 표기법을 가장 먼저 이야기 했어야 했는데, 마지막에 적게 되었네요. 지난 글, 시간 복잡도에서 알고리즘을 평가할때 최선의 경우와 평균의 경우 그리고 최악의 경우를 나눈다고 했는데요. 빅오 표기법은 일반적으로 많이 사용되는 표기법이고 최악의 경우를 나타냅니다. (시간 복잡도에서 가장 많이 쓰이는 표기법이라고 하네요.)
오.. 정렬 알고리즘 quick sort의 경우는 예외적으로 평균의 경우(O(nlogn))를 빅오 표기법으로 사용한다고 합니다.
여기에서 O는 order 이라고 읽는 것이라고 합니다. 몇가지 표기법을 예로 들자면
2 = O(1)
log2n = O(logn)
n2+2n+5 = O(n2)
3n4+n2+5n+1 = O(n4)
성능의 순서는
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!) < O(nn)
항상 n만 사용되는 것은 아니고 O(AB), O(wh)등.. 다양하게 표현 될 수도 있다고 합니다.
그 다음으로 많이 사용되는 빅오 표기법의 종류에 대해 알아봅니다.
O(1)
여기서 1은 숫자 1을 나타내기 보단 상수를 의미하는데요. 입력되는 데이터의 량과 상관없이 일정한 횟수로 실행 되거나 한 단계만을 거치는 것을 말합니다.
O(logn)
이전 글에서 log에 대해 살짝 이야기한 적이 있는데요. 데이터의 증가량에 따라 연산 수나 단계가 늘어나지만 그 양이 n보다는 적습니다. 주로 커다란 문제를 일정한 크기를 갖는 작은 무제로 쪼갤때 나타난다고 합니다. 이전글의 예로 들면 n은 모든 n의 실행이라면 logn은 n의 제곱마다 실행된다거나 뭐 그런식??
O(n)
가장 이해하기 쉬운게 n이 아닐까 싶어요, 데이터의 양에 따라 정비례하게 증가합니다.
O(nlogn)
시간 복잡도로 n * logn 가 나올때 쓰는 표기법이 아닌가 싶어요. O(n)보다는 많이 실행 되지만 O(n2)보다는 적게 실행되는 그 사이??
O(n2)
데이터에 양에 따라 걸리는 시간이 제곱에 비례하는 것을 말합니다. n번 반복되는 반복문이 2번 중첩될 때 겠죠?
빅오 표기법을 제외하고도 몇가지 표기법이 더 있는데요.
빅오메가 표기법
빅오 표기법이 최악의 경우를 나타내는 표기법이라면, 빅오메가 표기법은 그 반대로 최선의 경우를 나타내는 표기법입니다.
빅세타 표기법
마지막으로 빅세타 표기법이 있는데요. 빅세타는 빅오와 빅오메가의 공통되는 부분, 최소와 최악의 중간인 평균적인 표기를 나타냅니다.
