[공학]분할 및 정복 ( Divide-and-Conquer ) 의 모든 것

소개

분할 및 정복 ( Divide-and-Conquer )에 대한 발표자료 입니다.
정말 열심히 조사한 것이라 빠짐없이 완벽한 레포트 입니다.
또한, 여러 알고리즘들을 철저하게 분석해 보았습니다.

목차

3. 1 분할 및 정복의 개념
3. 2 이진탐색(binary search)
3. 3 strassen의 행렬식 곱셈 알고리즘
3. 4 최대값 및 최소값 문제
3. 5 합병정렬(merge sort)
3. 6 퀵 정렬(quick sort)

본문내용

▣ 개 요
: 일반적인 행렬(n×n)의 곱셈은 Θ(n3)의 시간을 필요로 한다.
그러나, Strassen에 의한 알고리즘에 의하면 행렬곱셈을
Ο(n2.81)의 시간에 해결할 수 있습니다.
Strassen의 행렬곱셈의 내용과 Strassen 알고리즘의 시간
복잡도가 Ο(n2.81)가 됨을 살펴 보겠습니다.

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

▣ n x n 행렬을 Strassen의 행렬 곱셈 알고리즘을 구하는 기본 생각
- 가정 : n은 2의 거듭제곱(지수)이다.

T1 = ( A11 + A22) ( A11 + A22)
T2 = ( A21 + A22) B11
T3 = B11 ( B12 + B22)
T4 = A22 ( B21 + B11)
T5 = ( A11 + A12) B22
T6 = ( A21 – A11) ( B11 + B12)
T7 = ( A12 - A22) ( B21 + B22)

알고리즘 3.2 : 두 개의 n x n 정방행렬에 대한 곱셈 알고리즘
문제 : n이 2의 지수일 때, 두 개의 n x n 정방행렬의 곱셈을 구하시오.
입력 : 2의 지수인 자연수 n 및 두 개의 n x n 정방행렬 A와 B
출력 : A와 B를 곱한 결과의 행렬식 C

참고자료

· 없음