분야
zipheadnode *Get_TransposeMatrix(headnode *head); // 전치행렬을 만드는 함수
void Get_ResultOfMultiplication(headnode *MatrixA, headnode *MatrixB); // 두 희소행렬을 곱해주는 함수
void fprint_Matrix(headnode *head); // 행렬을 출력해주는 함수
void fprint_WholeResult(headnode *MatrixA, headnode *MatrixB, headnode *Result); // 사용된 모든 행렬을 출력해주는 함수
nodeptr makenode(int i, int j, float val, nodeptr nextcol, nodeptr nextrow); // 리스트의 노드를 생성하는 함수
headnode *init_sparse_array(int n, int m); // 헤드노드를 생성하는 함수
nodeptr Make_SparseMatrix(headnode *s, nodeptr current_node, int r, int c, float v); // 희소행렬의 원소를 리스트에 삽입하는 함수
void Delete_Matrix(headnode *t); // 희소행렬 리스트를 삭제하는 함수
위 소스의 시간복잡도의 경우 곱셈을 수행하는 과정에 영향을 받으므로 이를 분석한다. 우선 행렬A의 행사이즈를 n, 열사이즈를 m,
행렬B의 행사이즈를 m, 열사이즈를 l이라 한다. 곱셈 수행 함수가 호출되면 전치행렬을 생성하게 되는데 전치행렬을 만드는 함수의
경우 두개의 for문에 의하여 시간복잡도가 좌우된다. 전치행렬생성 함수의 첫 for문은 행렬B의 열사이즈 만큼 수행된다. 따라서 l번
수행된다고 할 수 있다. 내부 for문의 경우 원소의 갯수만큼 수행되는데 best case는 0, worst case는 행렬B의 행사이즈인 m이 된다.
따라서 평균적으로 m/2만큼 수행된다고 할 수 있으며, 시간복잡도를 구하면 l*m/2가 되고 Big-Oh notation으로 표현하면 O(m*l)이다.
전치행렬이 생성되면 계산을 위한 while문으로 들어가는데 외부 while의 경우 best case는 모든 원소가 없는 경우로서 0번이며,
worst case는 원소가 꽉 차이있는 경우로서 결과행렬의 크기인 n*l번이 수행된다. 내부 while의 경우 행렬A의 열사이즈 및 전치행렬의
열 사이즈 만큼 수행되는데, best case는 원소가 없는 경우로서 무조건 1번 수행 되므로 1이 되며, worst case는 원소가 가득 찬 경우
로서 m이 된다. 따라서 총 시간복잡도는 O(n*m*l)이다. 위 전치행렬을 구하는 구간 및 계산 구간을 고려한 곱셈 함수의 총 시간복잡도
는 n*m*l + m*l이 되며, 이를 Big-Oh notation으로 표현하면 m*l이 무시되어 O(n*m*l)이다.
2. 공간복잡도 분석
위 소스에서는 동적으로 메모리를 할당하여 이용하는 리스트가 총 4개이며, 이는 행렬A, 행렬B, 전치행렬, 결과행렬을 위한 공간이다.
여기서 전치행렬은 행렬B와 같은 공간을 사용하므로 제외하고, 나머지 행렬들이 사용하는 원소노드의 갯수를 n1, n2, n3라고 할때, 헤드
노드를 위한 공간 1, tail노드 공간 1, 인덱스를 위한 공간의 경우 행렬A는 n+m, 행렬B는 m+l, 결과행렬은 n+l을 차지하게 된다. 따라서
리스트에 의한 총 사용공간은
행렬A공간 + 행렬B공간 + 전치행렬공간 + 결과행렬공간 = n+m+m+l+l+m+n+l+n1+n2+n2+n3+8 = 2*n+3*m+3*l+n1+2*n2+n3+8
이 되며, 이를 Big-Oh notation으로 표현하면 상수부분이 무시되므로 O(n+m+l+n1+n2+n3)이 된다.
3. 함수 설명
(1) int Get_MatrixFromFile();
이 함수는 파일로 부터 행렬을 받아오는 경우 사용되는 함수이다.함수가 호출되면 파일 array.dat를 열어 첫 열에서 행/열/원소의
갯수를 받아와서 저장한다.그 후 원소의 갯수에 따라서 파일상에서 각 원소 저장에 필요한 데이터를 받아온다. 이러한 방식으로 두
행/렬을 모두 받아오면 전치행렬을 생성하고 곱셈을 하기위한 함수를 호출해 준다.
(2)headnode *Get_TransposeMatrix(headnode *head);
파라미터로 받아온 행렬의 전치행렬을 생성하여 리턴해주는 함수. 전달받은 행렬의 열값을 행 사이즈로 하여 첫 for문을 돌리고,
내부 for문은 전달받은 행렬의 행값을 조건을 돌아간다. 첫 for문에서 저장할 노드를 열의 인덱스를 기준으로 설정하며, 내부
for문에서 Make_SparseMatrix함수를 이용하여 원소가 존재하는 경우 저장을 하게된다. 내부 for문의 카운터는 원소의 갯수 만큼만
수행될 수 있도록 현재 노드의 row값을 기준으로 변경되게 된다.
(3)void Get_ResultOfMultiplication(headnode *MatrixA, headnode *MatrixB);
파라미터로 전달 받은 두 행렬을 곱하고 그 결과를 출력하는 함수. 함수가 수행되면 A행렬의 열 사이즈와 B행렬의 행사이즈를
비교하여 정상적인 두 행렬인지 확인한 후 곱셈을 수행. 곱셈은 전치행렬을 이용하므로 전치행렬 생성함수를 호출하고 생성이
끝나면 계산 시작. 결과행렬에 저장될 위치는 Rrow로 행, Rcol로 열을 유지하여 준다. current_Rnode로 현재 노드를 유지하면서
Make_SpaseMatrix함수를 이용하여 각 결과 노드를 저장한다. 첫 while문은 결과노드의 행변수인 Rrow가 범위를 벗어나는 경우
멈춘다. 내부 while은 A행렬의 행과 전치행렬의 지정된 행을 곱하여 sum에 저장해주는 기능을 하며, 두행렬 중 하나라도 해당
행에 원소가없는 경우는 수행되지 않는다. 계산은 현재 두 행렬의 노드의 열값이 동일한 경우만 수행되며, 그렇지 않은 경우
작은 열값을 갖고 있는 노드를 다음노드로 이동 시키서 수행된다. 결과행렬의 열입력위치 변수 Rcol이 열사이즈를 벗어나면 Rrow를
증가 시키고 Rcol 및 전치행렬의 행을 지정하는 변수 i를 0으로 초기화 시켜준다. 계산이 끝나면 결과를 출력하여 준다.
(4)void fprint_Matrix(headnode *head);
행렬의 전체 모습을 출력하는 함수. 희소행렬 상에 원소가 없는 경우는 0을 출력하여 준다.
(5)void fprint_WholeResult(headnode *MatrixA, headnode *MatrixB, headnode *Result);
프로그램에 사용된 모든 행렬의 모습을 출력하는 함수.
(6)nodeptr makenode(int i, int j, float val, nodeptr nextcol, nodeptr nextrow);
희소행렬의 각 노드를 생성하고 다음 노드와 연결하는 함수. 파라미터로 받아온 행/열/원소를 저장한 노드를 생성하고 다음노드의
주소와 연결시켜 준다.
(7)headnode *init_sparse_array(int n, int m);
희소행렬로 이용될 리스트의 헤드를 생성하는 함수. 첫 노드에는 행/열사이즈 및 원소의 갯수가 들어있다. rows 및 cols는
각 행렬의 인덱스 역할을 하게되며, 각 행/열의 첫 노드 또는 tail과 연결되게 된다.
(8)nodeptr Make_SparseMatrix(headnode *s, nodeptr current_node, int r, int c, float v);
희소행렬 리스트에 원소를 삽입하는 함수. 파라미터로 받아온 현재 위치의 다음 또는 새로운 위치에 노드를 생성하여 삽입하여 주고
현재 위치를 변경하여 리턴.
(9)void Delete_Matrix(headnode *t);
희소행렬을 저장한 리스트를 삭제해주는 함수. 각 희소행렬은 헤드노드, 행/열의 인덱스 배열, 원소들의 노드, tail을 갖고 있으므로,
이를 차례로 지워준다. 먼저 각 노드들을 헤드에 저장된 원소의 갯수만큼 whil을 수행하여 지워주고, tail을 삭제하여 준다. 다음으로
각 인덱스 배열들을 헤드노드의 행/열 사이즈를 조건으로 삭제하여 주고, 헤드를 삭제한다.
전치행렬을 생성하여 곱셈 수행 후 파일로 결과 출력
