Big-O 표기법과 시간 복잡도

프로그램은 방식에 따라 실행 시간을 줄일 수도 있다. 그리고 big-o표기법에 대해서 잘 관찰하면 보통 반복과 같은 형태에서 나타난다.
한 줄의 실행에 n으로 표기하고, O(n)으로 표기한다. 그리고 n은 큰수라고 가정하기 때문에
O(an+b)와 O(n)은 같은 것으로 간주한다.
주요한 것은 실행시간이 선형적이라는것뿐이다.
보통 O(logn) < O(n) < O(n^2) < O(2^n)
으로 표기하곤 한다. 입력크기 n이 커질때 알고리즘의 실행 시간이 어떻게 변하는지를 나타내므로 최악의 경우를 나타냅니다. 그러므로 n이 충분이 클때로 생각합니다.

희소 행렬과 그 표기

희소행렬이란 행렬의 원소값들 중 0이 많은 행렬을 희소행렬이라 합니다. 대부분의 요소가 0이므로, 메모리 절약에 도움이 됩니다. 따라서 일반 행렬과는 표기도 다르게 함이 옳습니다.
그러므로 <행,열,원솟값> 으로 표기한다.
코드로 표기하면 다음과 같다.

typedef struct {
  int row;
  int col;
  int value;
} term;

다음처럼 표기하여 value의 기본값을 0으로 저장한 뒤에 value의 값이 0이 아니면 (0,0,15)라면 1행1열의 원솟값은 15라는 것이다

희소행렬의 전치의 일반적 표기법과 시간 복잡도

희소행렬에서 시간 복잡도를 감안하지 않고 행렬을 전치시켜보자.

term a[MAX_COL];
term b[MAX_COL];
void transpose(term a[], term b[]){
  int n, i, j, currentb;
  n = a[0].value;
  b[0].row = a[0].col;
  b[0].col = a[0].row;
  b[0].value = n; // b값 처리
  if(n > 0){
    currentb = 1;
    for(i=0;i<a[0].col;i++){
      for(j=1;j<n;j++){
        if(a[j].col == i){
          b[currentb].row = a[j].col;
          b[currentb].col = a[j].row;
          b[currentb].value = a[j].value;
          currentb++;
        }
      }
    }
  }
}

코드를 이해하고, 코드의 시간 복잡도를 분석해보겠습니다.
a에서 b로 전치시키는 것이 목적입니다.
값은 a[0].value = 총 0이 아닌 원소값의 합.
b[i].col에는 a[i].row대입하고
row에는 col을 대입합니다.
그리고 a의 열갯수 배열의 총 원소 수 를 곱한 번 만큼 반복하여
a[j].col이 i와 같을 때,
i와 값을 전치하여
terms b[]에 저장합니다.
이때는 column 수가 많을수록 시간복잡도가 커집니다.
시간복잡도는 다음과 같이 계산합니다. value = 총 원소수
총 원소수 = row col 이므로
반복량은 row row col 이다.

조금 반복량이 많은 거 같다. 더 줄일 반복은 없을까? 한번 코드를 줄여보자.

희소행렬의 전치를 빠르게 실행시키는 방법과 그 시간 복잡도

term a[MAX_COL]; // 입력 행렬
term b[MAX_COL]; // 전치 행렬
void fast_transpose(term a[], term b[]){
  int row_terms[MAX_COL], starting_pos[MAX_COL]; 
  int i,j,num_cols,num_terms=a[0].value; // row_terms는 각 행렬의 원소 개수를 저장, starting_pos는 각 열의 시작 위치, num_cols는 열의 개수, num_terms는 행렬의 항의 수
  b[0].row = num_cols; b[0].col = a[0].row; // 전치행렬 선언
  b[0].value = num_terms;
  if(num_terms > 0 ) { // 항목이 하나 이상있을 경우에만 수행
    for(i=0; i<num_cols; i++){ // row_terms를 초기화
      row_terms[i] = 0;
    }
    for(i=1; i<=num_terms; i++){ // 값을 대입함
      row_terms[a[i].col]++; // row_terms에 각 행렬의 원소 개수를 저장
    }
    starting_pos[0] = 1; // starting_pos를 초기화 , 첫 항목을 1로 설정 왜냐? 
    for(i=1; i<num_cols; i++){ // starting_pos를 계산 값은 이전 열의 시작 위치와 항의 수를 더한 값
      starting_pos[i] = starting_pos[i-1] + row_terms[i-1];}
    for(i=1; i<=num_terms; i++){ // a를 탐색하여 전치된 위치에 b배열에 저장 적절한 위치를 결정하고 해당 위치에 값을 저장하고 시작 위치를 증가시킴
      j = starting_pos[a[i].col]++;// starting_pos를 사용하여 시작 위치를 증가시킴
      b[j].row = a[i].col;
      b[j].col = a[i].row;
      b[j].value = a[i].value;
    }
  }
}

시간 복잡도를 줄여보았습니다. 코드를 해석해보겠습니다.
아까완 다르게 값을 n을 통해 선언하지 않고 starting_pos, num_terms 를 통해서 starting_pos에는 각 열에 시작 위치를 저장하고, num_terms 에 각 열에 몇개의 0이 아닌 원소가 들어가는지 저장합니다.
terms a[]에 저장된 값을 전치하려면 행과 열을 행과 열을 서로 바꿔야 합니다. 시작 위치는 1입니다. 만약 4 x 3의 행렬 이라 가정합니다.
0 0 3 0
2 5 0 0
0 0 0 15
이라면 표기를 (0,2,3), (1,0,2),(1,1,5),(2,3,15) 로 표기합니다
그러면 row_terms의 초깃값이 {1,1,1,1} 이고
startring_pos의 초깃값을 1로 설정하고 합연산을 시키므로 {1,2,3,4}가 된다.
num_term으로 반복하고 starting_pos(a[i].col)값을 하나씩 증가시켜 대입합니다.
(0,2,3), (1,0,2),(1,1,5),(2,3,15) 이 경우에는 (0,2,3)을 먼저 실행하므로
(a,b,c,d)가 있을때 (a,b,c+1,d)가 되고 (a+1,b,c+1,d) .. (a+1,b+1,c+1,d+1)이 된다.

그럼 시간 복잡도를 분석해보겠습니다.
for문이 4개 있고 각각 col반복이 두개, elements반복이 두개이므로
O(2(columns+elements))이다 elements = row x columns이다
어차피 계수는 무시하므로 O(columns+ row columns)이다
O(columns row)이므로
위의 값보다 시간 복잡도가 더 빠릅니다.