후하하핫
9k
2022-03-24 06:53:38
3
4387

시간복잡도와 공간복잡도에 대해: 댓글 쓰다 날아가서 빡쳐서 쓰는 칼럼


후... 댓글을 1시간 가량을 들여 길게 썼는데 timeout으로 다 날아가 버렸습니다. 진짜 빡치네요. 그래서 많은 분들 보시라고 칼럼에 씁니다. 다음 글에 대한 답변입니다: https://okky.kr/article/1185786


0. 질문은 아래 코드에 대한 시간 복잡도를 물어보셨습니다.


function printFirstItem(items) {
  console.log(items[0]);

  let middleIndex = Math.floor(items.length / 2);
  let index = 0;

  while (index < middleIndex) {
    console.log(items[index]);
    index++;
  }

  for (let i = 0; i < 100; i++) {
    console.log(hi);
  }


1. 일단, 가장 간단한 답은 O(n)입니다만, 질문자 분은 이런 답을 바라시지 않고 저 정확히 왜 O(n)인지를 물어보셨습니다. 항상 저는 그렇지만, 쓸데없이 긴 답변을 답니다.


2. f(n) = O(g(n)) 이란 무엇인가

함수 f(n)이 있을 때, f(n) <= c * g(n)을 만족시키는 0보다 크거나 같은 n의 값 n0과 실수 c, 단조증가하는 함수 g(n)이 존재하면 f(n)은 O(g(n))에 속한다고 합니다. 그림으로 그리면 다음과 같습니다.

Big-O Notation, Omega Notation and Big-O Notation (Asymptotic Analysis)

즉, f(n)이 cg(n)에 비해 특정 지점 (n0) 이전에는 작든 크든, 그 이후부터는 무한대로 갈 때까지 계속 값이 큰 경우가 f(n) = O(g(n)) 의 의미입니다. 말이 어렵죠? 쉽게 말하면 f(n)은 어떤 지랄을 해도 g(n)보다 작을 수 밖에 없는, 알고리즘의 용어로 옮기면 데이터가 무한히 많이 들어오는 최악의 경우에 f(n)이라는 알고리즘의 연산의 수가 g(n)이라는 함수보다 적을 수 밖에 없는 경우를 뜻합니다. 이때 g(n)을 upper bound라고 말합니다.


이래도 어려운걸 압니다. 게다가 아직 알고리즘 얘기는 시작도 안했고요.


3. 알고리즘에는 시간복잡도와 공간복잡도라는 개념이 있습니다. ("복잡도" 라는 이름에도 히스토리가 있긴 한데, 그건 넘어갑시다)


이걸 얘기하기 전에, 특정 알고리즘의 성능을 평가하는 방법에 대한 얘길 해보죠.


가장 널리 쓰이는 방법은 "계측", 즉 알고리즘 돌려보고 시간 측정하는 방법입니다. 이 방법이 개념적으로 직관적이기도 하고, 그냥 코드 몇줄 짜서 elapsed time만 보면 성능이 나오기 떄문에 많이 씁니다만, 이 방법은 측정마다 값이 달라지고 환경에 따라 큰 영향을 받기 때문에 학문적으로 다루기 좋은 값이 아닙니다.


이러한 문제를 해결하기 위해 알고리즘 학자들은 연산의 숫자를 셉니다. 알고리즘 하나에서 곱하기 몇개, 더하기 몇개가 있는지를 세서, 곱하기와 더하기 개수가 많으면 이 친구는 더 느린 알고리즘, 반대의 경우에는 빠른 계산이고, 무한히 데이터가 많을 때 곱하기와 더하기의 개수를 통해 나타내지는 함수가 알고리즘의 성능이라는 맘편한 주장을 합니다. (제 관점에서는 바보같은 소리로 들립니다. 그 이유는 나중에...)


그래서 이러한 기준으로 알고리즘의 성능을 평가하는 방법을 시간복잡도 (time complexity) 라고 부르고, 이것들을 asymptotic notation, 즉, 위에서 소개한 Big-Oh 든, small-oh 든, Big-omega 등 다양한 방법으로 "대충" 나타냅니다.


4. 이 Big-Oh notation으로 한번 질문 주신 분의 알고리즘의 성능을 평가해보죠.


먼저, asymptotic notation으로 나타내기 전에 연산의 단위를 정의해야 합니다. 저는 대입, 출력, 곱셉, 나눗셈, 비교, increment (++ 등) 을 연산으로 정의하겠습니다. 한번 손으로 세어보죠.


function printFirstItem(items) {
  console.log(items[0]); // 출력 1번.

  let middleIndex = Math.floor(items.length / 2); // floor 연산은 정의하지 않았으니 빼고, items.length / 2 는 나눗셈 1번.
  let index = 0; // 대입 1번.

  while (index < middleIndex) { // 비교 n / 2번.
    console.log(items[index]); // 출력 n / 2번.
    index++; // Increment n / 2번.
  }

  for (let i = 0; i < 100; i++) { // 대입 1번. 비교 100번, increment 100번.
    console.log(hi); // 출력 100번.
  


총 1 + 1 + 1 + n / 2 + n / 2 + n / 2 + 1 + 100 + 100 + 100 = n * 3 / 2 + 304 번의 연산을 하네요. n은 items의 길이이구요. 즉, f(n) = n * 3/2 + 304 입니다.


자, g(n), c, n0만 구하면 Big-Oh notation으로 나타내 볼 수 있습니다. 저는 c = 2, g(n) = n, n0 = 1000000 이라고 하겠습니다. (계산 귀찮...)


우리가 판단해야 하는 것은 n0 = 1000000일 때 f(n) <= c*g(n) 인가겠죠?


계산기 떄려보니 f(n0=1000000) = 1,500,304입니다. cg(n) = 2,000,000 이네요. n은 단조증가함수이므로, n0의 이상인 모든 수에서 cg(n)은 f(n)보다 크네요. 그래서 f(n) = O(n) 입니다. 쉽죠?


5. 칼럼으로 간 김에, 하나를 더 쓰면, 가장 박혀있는 오개념 중 하나가 시간 복잡도가 높은 알고리즘이 더 빠르다는 것입니다. 과연 그럴까요?

quicksort 는 최악의 경우 O(n^2) 이고, mergesort는 최악의 경우 O(nlogn) 입니다. 근데 quicksort는 평균적인 입력 (보통 amortized case라고 부릅니다) 에서 O(nlogn) 이라서 mergesort와 시간 복잡도가 같습니다. 그러면 mergesort나 quicksort나 비등비등 한걸까요?


quicksort는 pivoting이라는 작업을 합니다. (이것까지 쓰면 그냥 알고리즘 강의가 되니 패스... 한번 찾아보시길 바랍니다) 이 pivoting이 잘 될경우, asymptotic notation 상으론 구리지만 실제로 성능 함수 f(n)의 상수 값이 mergesort에 비해 좋습니다. 그래서 많은 경우 internal sorting을 하면 (쉽게 말해서, 메모리 안에서만 소팅을 한다면) mergesort보다 quicksort가 더 빠릅니다.


실제로 C++의 std::sort 함수를 까보시면 introspective sort 라는 알고리즘을 쓰는데, 얘 자체가 quicksort를 기본으로 합니다. (정확히는 quicksort로 가다가 이 친구의 traversal tree의 depth가 log n을 넘어가면 heap sort로 바꾸고, 특정 개수 미만일 때 insertion sort로 바꿉니다. 궁금하신 분들은 다음 링크 참고하세요. https://en.wikipedia.org/wiki/Introsort


이 이유 자체가, 조건만 맞으면 quicksort가 겁나 빠르기 때문입니다. 느린 경우에는 nlogn 정렬인 heapsort를 쓰는거구요. 거의 다 정렬이 되고 몇개 안된 상황에서는 O(n^2)인 insertion sort가 빠릅니다. 즉, 알고리즘의 성능을 고작 시간복잡도로 판단하는건 매우 큰 오산입니다.


이외에도 행렬의 곱셈을 알고리즘 시간에 배울 떄 Strassen's algorithm이라는 놈을 배우는데, 이 친구는 시간 복잡도가 O(n^3)보다는 낮은 알고리즘입니다. 얘보다 더 시간복잡도가 좋은 이론적인 알고리즘들이 있는데, 실제 돌릴땐 얘보다 느려서 안씁니다. 당연히도, 차원이 낮은 행렬의 곱셈에서는 얘보다 좋은 알고리즘이 너무 많아서 또 얘를 안씁니다. 즉, 시간복잡도는 그냥 참고사항이지, 성능 그 자체가 아닙니다.


6. 마치며


알고리즘 공부를 하시는 분들을 위해 충언을 하나 하자면, 알고리즘 잘하려면 공부를 딥따 많이 하셔야 합니다. 얘는 그냥 이론만 파고 수학만 잘하고 머리만 좋다고 잘 풀리는게 아니라, 코딩도 정말 잘 해야하고 이게 실제 상황에서 어떻게 굴러갈지에 대한 파악을 잘하셔야 합니다.


절대로 알고리즘 풀 때 그냥 풀지 마시고, 문제를 풀기 위한 방법론들에 과몰입하지 마세요 (탑코더에서 이런 바보들을 자주 만납니다 ㅎㅎ). 출제자의 의도를 파악하느라 시간 낭비하지 마시고, 진짜 얘 가지고 풀 수 있는 문제들이 뭔지 생각해보세요.

3
  • 댓글 3

  • monotonicity
    300
    2022-03-24 07:49:33
  • siyex42080
    505
    2022-03-27 15:02:19

    amortizedaverage는 다릅니다. 예로 드신 퀵소트 O(nlogn)의 경우는 average지 amortized가 아닙니다.

  • siyex42080
    505
    2022-03-27 15:12:56

    간단한 예를 들자면 동적 배열(자바의 ArrayList)의 끝에 값을 추가하는 경우는 때로는 O(N), 때로는 O(1)이지만 여러번 추가 하여 평균을 내는 경우 (amortized) 어떤 순서로 어떤 데이터를 집어넣더라도 운의 개입 여지 없이 O(1) 입니다. 평균적으로는 O(N log N)이지만 운의 영향을 받아 언제든 O(N^2)이 될 수 있는 퀵소트와는 다릅니다.

  • 로그인을 하시면 댓글을 등록할 수 있습니다.