희소행렬 전치 + 빠른 전치

희소행렬 전치

시간복잡도 O(Col X Terms)

#include <stdio.h>
#define MAX_TERMS 101

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


typedef struct SparseMatrix {
	element data[MAX_TERMS];
	int rows; // 행의 개수
	int cols; // 열의 개수
	int terms; // 항의 개수
} SparseMatrix;


SparseMatrix matrix_transpose2(SparseMatrix a) {
	SparseMatrix b;
	int bindex; // 행렬 b에서 현재 저장 위치
	b.rows = a.rows;
	b.cols = a.cols;
	b.terms = a.terms;
	if (a.terms > 0) { //0 이상일 때만
		bindex = 0;
		for (int c = 0; c < a.cols; c++) {
			for (int i = 0; i < a.terms; i++) {
				if (a.data[i].col == c) {
					b.data[bindex].row = a.data[i].col;
					b.data[bindex].col = a.data[i].row;
					b.data[bindex].value = a.data[i].value;
					bindex++;
				}
			}
		}
	}
	return b;
}

void matrix_print(SparseMatrix a) {
	printf("====================\n");
	for (int i = 0; i < a.terms; i++) {
		printf("(%d, %d, %d) \n", a.data[i].row, a.data[i].col, a.data[i].value);
	}
	printf("====================\n");
}


int main() {
	SparseMatrix m = {
		{{0,3,7},{1,0,9},{1,5,8},{3,0,6},{3,1,5},{4,5,1},{5,2,2}},
		6,
		6,
		7
	};
	matrix_print(m);
	SparseMatrix result;
	
	result = matrix_transpose2(m);
	matrix_print(result);
	return 0;
}

 

희소행렬 빠른 전치

O( Cols + Terms)
빠른 전치의 핵심은 '내가 찾으려고 하는 column이 몇개씩 있고 어디부터 시작하는지 알아낸 다음에 탐색 시작하자'입니다. 이로써 시간복잡도가 많이 줄어들게 됩니다.✌✌ (공간복잡도는 조금 늘어나긴 합니다ㅠㅠ)

#include <stdio.h>
#define MAX_TERMS 101
#define MAX_COL 51
typedef struct {
	int row;
	int col;
	int value;
} element;


typedef struct SparseMatrix {
	element data[MAX_TERMS];
	int rows; // 행의 개수
	int cols; // 열의 개수
	int terms; // 항의 개수
} SparseMatrix;


SparseMatrix fast_matrix_transpose(SparseMatrix a) {
	SparseMatrix b;
	int row_terms[MAX_COL] = {}, starting_pos[MAX_COL] ;
	int  i, j, num_cols = a.cols, num_terms = a.terms;
	b.rows = num_cols;
	b.cols = a.rows;
	b.terms = num_terms;
	if (num_terms > 0) {	/* nonzero matrix  */
		for (i = 0; i < num_terms; i++)
			row_terms[a.data[i].col]++; //해당 col이 몇 개씩 존재하는지 적기
		//col의 갯수에 맞추어 시작 지점을 기록해둔다.
		starting_pos[0] = 0;  
		for (i = 1; i <= num_cols; i++)
			starting_pos[i] = starting_pos[i - 1] + row_terms[i - 1];
		for (i = 0; i < num_terms; i++) {
			j = starting_pos[a.data[i].col]++;
			b.data[j].row = a.data[i].col;
			b.data[j].col = a.data[i].row;
			b.data[j].value = a.data[i].value;
		}
	}
	return b;
}

void matrix_print(SparseMatrix a) {
	printf("====================\n");
	for (int i = 0; i < a.terms; i++) {
		printf("(%d, %d, %d) \n", a.data[i].row, a.data[i].col, a.data[i].value);
	}
	printf("====================\n");
}


int main() {
	SparseMatrix m = {
		{{0,3,7},{1,0,9},{1,5,8},{3,0,6},{3,1,5},{4,5,1},{5,2,2}},
		7,
		7,
		7
	};
	matrix_print(m);
	SparseMatrix result;

	result = fast_matrix_transpose(m);

	matrix_print(result);
	return 0;
}

위 코드에서 row_terms와 starting_pos에 해당하는 내용입니다.