[공학]분할 및 정복 발표 보고서

목차

1. 보고자
2. 발표 주제
3. 발표 내용
1. 3.3 Strassen의 행렬식 곱셈 알고리즘
2. 3.4 최대값 및 최소값 문제
3. 3.5 합병정렬(merge sort)
4. 결론 도출

본문내용

2. 발표 주제
o 3. 3 Strassen의 행렬식 곱셈 알고리즘
o 3. 4 최대값 및 최소값 문제
o 3. 5 합병정렬(merge sort)

3. 발표 내용
1. 3.3 Strassen의 행렬식 곱셈 알고리즘
- 개 요
: 일반적인 행렬(n× n)의 곱셈은 Θ(n3)의 시간을 필요로 한다. 그러나 Strassen에 의한
알고리즘에 의하면 행렬곱셈을 Ο(n2.81)의 시간에 해결할 수 있다.
이번 장에서는 Strassen의 행렬곱셈의 내용과 Strassen알고리즘의 시간 복잡도가 Ο(n2.81)이
됨을 살펴본다.

[ 그림 1 ] [ 그림 2 ]

두 개의 2 x 2 정방행렬의 결과 값의 원소가 있는 C 행렬의 각원소의 값을 구한다고 하자[그림 1].
우리는 각 원소 값 C11, C12, C21, C22을 구하기 위해서 [그림 2]와 같은 과정을 반복하여야 할 것이다.
여기서, 우리는 하나의 행렬 원소의 값을 구하기 위해서는 2번(n)의 곱셈과 한번(n-1)의 덧셈 연산이 필요함을 알 수 있다. 이는 전체 계산결과 행렬 C 의 각 원소가 4개(n x n)이므로 위의 과정을 4번 반복하게 된다. 따라서 재래식 방법으로 푼 두 개의 2 x 2 (n x n)행렬 곱셈은 총 8번(n3)하였으며, 덧셈 연산은 4번(n2(n-1))하였음을 알 수 있었다.
다음은 Strassen 방법으로 푼 2 x 2 행렬 곱셈을 구 해보자.


[ 그림 3 ]

[그림 3]에서 보는 것처럼 우선 행렬식 t1 ~ t7을 가정함으로서 출력결과 행렬 C 는 위와 같은 행력 식으로 표현할 수 있다. 이 방법으로 2 x 2 행렬 곱셈을 하면 총 7번의 곱셈연산과, 18번의 덧셈/뺄셈연산을 수행 하게 된다.

2 x 2 행렬 기준으로 비교하면
- Strassen은 7개의 곱셈과 18개의 덧셈/뺄셈이 요구된다.
- 재래식 곱셈 알고리즘은 8개의 곱셈과 4개의 덧셈/뺄셈이 요구됨
- 별로 향상된 점이 없음.
- 그러나 행렬의 크기가 커지면 성능은 달라진다.

참고 자료

없음