18. 희소행렬의 전치 (Fast Transpose)

이전 글에서 봐왔던 것처럼 일반적인 2차원 배열을 통한 행렬을 전치시키는 것은 O(row * col)만큼의 시간이 들어간다. 행렬이 희소행렬 표현법으로 표현된 경우 전치시키기 위해 O(col^2 * row)만큼의 시간이 들어간다. 즉, 저장 공간의 효율성을 위해 시간을 포기한 것이다. 그래서 일반적인 Transpose알고리즘 보다 빠른 전치 알고리즘을 사용한다.

---

희소행렬의 빠른 전치 (Fast Transpose 알고리즘)

희소행렬의 빠른 전치를 위한 알고리즘은 아래와 같다.

void Fast_Transpose(term a[], term b[]){
    int rowTerms[a[0].col], startingPos[a[0].col];
    int i, j, numCols = a[0].col, numTerms = a[0].value;
    
    b[0].row = a[0].col;
    b[0].col = a[0].row;
    b[0].value = a[0].value;
    
    if (numTerms <= 0) return;
    
    // 각 열마다 0이 아닌 원소가 몇개있는지 확인
    for(i=0; i<numCols; i++) rowTerms[i] = 0;
    for(i=1; i<=numTerms;i++) rowTerms[a[i].col]++;
    
    // 각 열의 시작 위치 확인
    startingPos[0] = 1;
    for(i=1; i<numCols; i++)
        startingPos[i] = startingPos[i-1] + rowTerms[i-1];
    
    // 희소 행렬 전치
    for(i=1;i<=numTerms;i++){
        j = startingPos[a[i].col]++;
        b[j].row = a[i].col;
        b[j].col = a[i].row;
        b[j].value = a[i].value;
    }
}

해당 알고리즘의 시간복잡도는 O(col + elements)로 행렬을 전치시킬 수 있다. rowTerms, startingPos 배열의 값을 하나하나 확인하면서 알고리즘을 풀어나간다면 쉽게 이해할 수 있을 것이다.