자바스크립트로 알아보는 알고리즘 #2 공간 복잡도, 빅오 표기법

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

1. 공간 복잡도

제가 공간 복잡도에 대한 이해가 부족하고, 블로그의 글들도 대부분 바로 빅오 표기법으로 알려주는 경우가 많아서 잘못된 부분이 많을 수 있습니다. 잘못된 부분은 댓글로 알려주시면 감사할 거 같아요…
추후에 공간 복잡도에 대해 확실히 공부를 해서 그때 다시 수정하도록 하겠습니다.

이전 글에서 살짝 이야기를 했었는데, 공간 복잡도는 알고리즘이 수행되는데 필요한 기억장치(메모리(RAM))의 크기를 이야기합니다.
우선 인터넷에서 찾아본 간단한 예를 살펴봅니다.

위 예의 경우 a, b, c는 3개의 변수로 메모리상 1씩 3개해서 3을 차지하는 것처럼 보일 수 있지만, 외부에서 인자로 받아오고 함수는 바로 리턴하기 때문에 공간 복잡도는 0입니다.
빅오 표기법으로는 O(1) 이려나요..?

위 예에서는 우선 변수 s를 초기화하는 1, 그리고 i를 초기화하는 1, 그리고 for문을 끝내기 위한 n값 1, 끝으로 반복문에서 arr[i]의 n값을 해서 총 공간 복잡도는 n + 3 이됩니다. (그런데 여기서 for문을 끝내기 위한 n의 값 1이 아직 이해가 잘 되지 않네요…)
빅오 표기법으로는 O(n) 일 거 같아요.

위 예가 시간 복잡도와의 차이를 잘 느끼게 해주는 거 같아요. 아마도 val 이라는 변수를 초기화 하는데 1, 그리고 반복문에 사용된 변수 i에 1. 그래서 반복문이 몇번 반복되는 것과 상관 없이 공간 복잡도는 2가 되고 빅오 표기법으로는 O(1)이 될 거 같아요.

위 예의 경우에는 n의 개수만큼 sample 함수가 반복 실행되겠죠? n개수 만큼 콜 스택이 쌓이기 때문에 위 공간 복잡도를 빅오 표기법으로하면 O(n)이 됩니다.

위 예는 단순히 함수가 호출되는 수 만큼 공간을 차지하지 않는다는 걸 알려주는 예 인거 같아요. innerSample이라는 함수는 n번만큼 호출되지만 리턴값이 result라는 하나의 공간에 들어가기 때문에 공간 복잡도는 result, innerSample() 해서 2이고 빅오 표기법으로는 O(1)이 되는 것 같습니다.

몇가지 예를 찾아보았는데요, 어느 정도 알 것도 같으면서 잘 모르겠네요.
다음에 서점에 가서 책으로 한번 다시 살펴보는게 좋을 거 같아요.

2. 빅오 표기법

지금 와서 생각해보니 빅오 표기법을 가장 먼저 이야기 했어야 했는데, 마지막에 적게 되었네요. 지난 글, 시간 복잡도에서 알고리즘을 평가할때 최선의 경우와 평균의 경우 그리고 최악의 경우를 나눈다고 했는데요. 빅오 표기법은 일반적으로 많이 사용되는 표기법이고 최악의 경우를 나타냅니다. (시간 복잡도에서 가장 많이 쓰이는 표기법이라고 하네요.)

오.. 정렬 알고리즘 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번 중첩될 때 겠죠?

3. 그 밖의 표기법

빅오 표기법을 제외하고도 몇가지 표기법이 더 있는데요.

빅오메가 표기법

빅오 표기법이 최악의 경우를 나타내는 표기법이라면, 빅오메가 표기법은 그 반대로 최선의 경우를 나타내는 표기법입니다.

빅세타 표기법

마지막으로 빅세타 표기법이 있는데요. 빅세타는 빅오와 빅오메가의 공통되는 부분, 최소와 최악의 중간인 평균적인 표기를 나타냅니다.

Leave a Reply

  1. 오류가있어요

    헝..근데 밑소스로 첫주를 하니깐 결과가 또 이상하네요ㅠㅠㅠㅠㅠㅠ 무튼 댓글폭탄이 된거같아서 죄송해요
    일단 다른 소스를 구해서 해야겠네요… ㅠ

    • 안녕하세요? 코드에 오류가 있었는데 오랫동안 몰랐네요…
      아래에 ‘더 좋은 방법’님이 알려주신 글을 참고해서 코드를 수정하였습니다.
      조금이나마 도움이 되었으면 좋겠네요~
      댓글 남겨주셔서 감사합니다 :)

  2. 오류가있어요

    제가 좀 수정을 해봤는데 일단 8월까지는 검증을 해봤어요. 근데 이후로는 어찌될지 모르겠네용..
    일단 첫 주랑 마지막 주 비교 후에 newDate에 i값을 더하셔서 그걸 newDate에 담으셨는데

    저는 첫 주, 마지막 주 비교 전에 newDate = (newDate + i);를 했습니다.
    그러고 첫 주, 마지막 주 비교할 때 변수명을 newDate로 바꿨어요.
    그러고 마지막 주 일 때 newDate = i; 대신에 newDate = newDate – nowLastDay;로 수정했습니다…

    수정된 for문 올릴게여… 근데 소스가 올라갈지 모르겠네요

    for (var i = -theDay; i < (theDay-7)*-1; i++){

    newYear = theYear;
    newDate = theDate;
    newMonth = theMonth;

    newDate = (newDate + i );
    // console.log(newDate);

    //첫주 일때
    if(newDate+i nowLastDay) {

    if(theMonth == 12){ // 12월 마지막주 일때
    newYear = Number(theYear) + 1;
    }

    newMonth = Number(theMonth) + 1;

    newDate = newDate – nowLastDay ;

    //console.log(“마지막 주 일 때 : ” + newMonth + “,” + newDate);
    }

    // yyyy-mm-dd 형식으로
    if(String(newDate).length < 2){
    newDate = "0" + String(newDate);
    }
    if(String(newMonth).length < 2){
    newMonth = "0" + String(newMonth);
    }

    //이번주 7일의 날짜를 value에 담는다.
    value.push(newYear + "-" + newMonth + "-" + newDate);
    }

  3. 오류가있어요

    안녕하세요.. 이거~ 이번주는 뭔가 이상하게 나오네요ㅠㅠ 이번주의 끝은 2017-07-01 이어야하는데
    2017-07-08로 계속 나옵니다… 소스 보고는 있는데 제가 만든게 아니라서 그런지 조금 어려운감이 있네요
    혹시 보게 되신다면 수정요청을 부탁드리겠습니다ㅠ

  4. 더 좋은 방법

    Date 객체의 function에 대한 이해가 잘 되어 있으면 코드량을 많이 줄일수 있습니다.

    http://pet2r.tistory.com/entry/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EA%B8%88%EC%A3%BC-%EA%B8%88%EC%9B%94-%EA%B5%AC%ED%95%98%EA%B8%B0

    시작일과 종료일만을 구하는 방법 이긴한데, 응용해서 사용하면 될 것 같네요.

    • 데이트 객체에 대해 한번 자세히 알아봐야겠어요ㅎ
      좋은 참고 글 감사합니다 :)

  5. 주인장님복받으세요

    ㅜㅜㅜㅜㅜ완전 감사합니다…진짜 복받으실거예용…

    • 안녕하세요~
      제가 너무 확인이 늦었네요… 도움이 되었다니 저도 기쁘네요.
      댓글 남겨주셔서 감사합니다 :)