이번 과제는 교재에 나오는 함수의 Flow Chart를 그리고

그 함수의 Time Complexity를 구하는 레포트입니다.

Flow Chart는 그려본지 오래되어 잠시 공부한 후 시작하였습니다.

사용한 프로그램은 Dia입니다.

해당 함수는 Sparse Matrix한 두 행렬의 곱을 구현하는 함수입니다.

처음에는 복잡하다는 생각이 들었으나

'내가 만약 행렬곱을 하는 함수를 만들면 무엇이 필요할까?'라는 생각을 하며

차근차근 밟아가니 어느 정도 이해할 수 있었습니다.

하지만 교재에 나오는 설명은 그리 도움이 되지 않더군요.

원판이나 번역판이나 무슨 말인지 모르겠습니다.;;;

무엇인가를 설명하려고하나 생략한 부분이 너무 많다는 느낌이었습니다.

사실 그러한 이유로 예전에 이 책으로 독학하기를 포기하였습니다.

밑에 레포트를 올립니다.^^

Flow chart

먼저 주석이 없는 Flow chart를 그렸습니다.

하지만 그 정보가 매우 미미하여 보기가 힘들 듯싶어 주석(annotation)을 달았습니다. 점선으로 표시한 것이 해당 명령어와 주석을 연결한 것입니다.

Time complexity

"fastTranspose(b, newB);"에서 b를 transpose하는데 O(colsB+totalB)의 complexity를 가집니다. 그리고 외부 루프인 “for (i = 1 ; i <= totalA ; )”에서는 totalA만큼 실행이 됩니다.

내부 루프인 “for (j = 1 ; j <= totalB+1; )”에서는 a행렬의 한 행과 b행렬의 모든 열(newB에서는 행)에 접근을 합니다. 행렬 a의 한 행과 행렬 b의 한 열의 내적(inner product)를 구하기 위해 행렬 a에서 한 행에 있는 0 아닌 value에 하나씩 접근합니다. 이런  value의 개수를 termsRow라고 한다면, i는 최대 termsRow만큼 증가합니다. termsRow만큼 진행하면 행렬 a의 현재 행을 다 보았다는 뜻이고 동시에 a[i].row는 다음 행을 가리키기에 “if (a[i].row != row)”가 TRUE가 되어 i를 rowBegin에 재설정하고 다음 열로 넘어갑니다. 이러한 작업은 행렬 a의 한 행에 관해 총 행렬 b의 열의 개수만큼 진행되므로 최대 colsB번 수행됩니다. 따라서 행렬 a의 한 행에 있어 i의 최대 총 증가량은 colsB*termsRow입니다. 앞에서 얘기했듯이 내부 루프는 a행렬의 한 행과 b행렬의 모든 열에 접근을 하기에 j의 최대 총 증가량은 totalB + 1입니다. 따라서 한 행이 곱해지는 동안 내부 루프에 소요되는 시간은 O(colsB*termsRow + totalB)입니다.

그 후 “for (; a[i].row == row ; i++)”이 최대 termsRow만큼 실행되어 rowBegin이 다음 행을 가리키도록 합니다. 따라서 이것에 소용되는 시간은 O(termsRow)입니다.

따라서 외부 루프가 한 번 반복하는데 걸리는 시간은 O(colsB*termsRow + totalB)이 되며, 이것이 행렬 a의 row 개수만큼 작동하므로 이 함수의 Time complexity는 다음과 같이 표시할 수 있습니다.

O(∑(colsB ? termsRow + totalB)) = O(colsB ? totalA + rowsA ? totalB)

느낀점

Flow Chart는 예전에 중학교 컴퓨터 시간에 잠깐 그려보고, 고등학교 수학 시간에 본 이후 한 번도 작성하거나 그려본 적이 없습니다. Flow Chart가 함수 상황을 한 눈에 들어오게 한다는 장점이 있지만, 그리기 힘들다는 것과 코드와 주석을 통해 그 뜻을 전달하는 것이 훨씬 효율적이지 않을까 하는 생각이었습니다. 그래서 이번 과제는 생각 외로 어려움이 많았습니다. 다행스럽게도 Flow Chart를 쉽게 그릴 수 있는 OpenSource 프로그램인 Dia라는 프로그램을 사용하여 큰 어려움은 없었습니다.

해당 코드

#define MAX_TERMS 101

#define COMPARE(x, y) (((x) < (y)) ? -1 : ((x) == (y))? 0 : 1)

void mmult(term a[], term b[], term d[])

{

  int i, j, column, totalB = b[0].value, totalD = 0;

  int rosA = a[0].row, colsA = a[0].col, totalA = a[0].value;

  int colsB = b[0].col, rowBegin = 1, row = a[1].row, sum = 0;

  int newB[MAX_TERMS][3];

  if (colsA != b[0].row)

  {

  fprintf(stderr, "Incompatible matrices\n");

  exit(EXIT_FAILURE);

  }

  fastTranspose(b, newB);

  a[totalA+1].row = rowsA;

  newB[totalB+1].row = colsB;

  newB[totalB+1].col = 0;

  for (i = 1 ; i <= totalA ; )

  {

      column = newB[1].row;

      for (j = 1 ; j <= totalB+1; )

      {

          if (a[i].row != row)

          {

              storeSum(d, &totalD, row, column, &sum);

              i = rowBegin;

              for (; newB[j].row == column ; j++)

                  ;

              column = newB[j].row;

          }

          else if (newB[j].row != column)

          {

              storeSum(d, &totalD, row, column, &sum);

              i = rowBegin;

              column = newB[j].row;

          }

          else switch (COMPARE(a[i].col, newB[j].col))

          {

              case -1:

                  i++; break;

              case 0:

                  sum += (a[i++].value * newB[j++].value);

                  break;

              case 1:

                  j++;

          }

      }

      for (; a[i].row == row ; i++)

          ;

      rowBegin = i; row = a[i].row;

  }

  d[0].row = rowsA;

  d[0].col = colsB;

  d[0].value = totalD;

}

- HOROWITZ ? SAHNI ? ANDERSON-FREED, <Fundamentals of Data Structures>, SILICON PRESS, 2008, pp. 81~82

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.