1. 이 절에서 사용된 표현에서 임의의 원소 A[i][j]를 찾아 그 값을 변경하는 데 소요되는 시간은 얼마나 되는가?
- 일반적인 방법 : O(cols*rows)
- 빠른 전치 행렬 : O(cols+terms)
3. 희소 행렬을 읽고 출력하는 C++ 함수를 작성하라. 이것은 <<와 >>를 다중화해서 구현되어야 한다. 입출력 형식을 설계해야 하지만 내부 표현은 이 절에서 사용된 0이 아닌 원소들의 1차원 배열을 사용하여야 한다. 이 함수들의 연산 시간을 분석하라.
*SparseMatrix 코드의 일부분 발췌
* 전체 코드는 첨부파일에
4. RowSize와 RowStart를 저장하기 위해 두 개의 배열을 사용하지 않고 단지 하나의 배열만을 사용하도록 FastTranspose 함수를 다시 작성하라.
//변경 전
// 변경 후
// 설명
rowSize와 rowStart를 하나의 배열 rowSizeStart로 묶어서 배열을 만들었음.
rowSize와 rowStart 둘 다 cols 사이즈의 배열이므로 rowSizeStrat는 cols*2의 크기로 배열을 만듦.
rowSizeStart[0 : cols-1] 은 rowSize에 해당하는 값.
rowSizeStart[cols : cols*2-1]은 rowStart에 해당하는 값.
6. FastTranspose에서 사용했던 행 포인터 개념을 사용하여 Multiply 함수(프로그램 2.14)를 2.4절에서와 같이 명시적으로 전치시키지 않고 두 희소 행렬을 곱할 수 있도록 다시 작성하라. 작성된 알고리즘의 연산 시간은 얼마인가?
* 6,7번은 2회독 때 다시 도전 ..
* 아쉽게도 아직 답안을 못 찾았음 ㅜ ㅜ..
* 배열의곱셈부터 제대로 이해하기 ..