3. Divide & Conquer
3.0 Introduction
3.1 Recurrence relation
3.2 Multiplication
3.3 Sorting
3.4 Medians
3.5 Matrix multiplication
3.1 Recurrence relation
Multiplication이란?
곱하기 연산을 의미한다.
<더하기 연산>
- 더하기 연산을 하게 될 때 O(n)의 시간복잡도를 갖는다.
<곱하기 연산>
- 곱하기 연산을 할 때 시간 복잡도는 O(n^2)이다.
<일반적인 방법으로 곱하기의 시간복잡도를 구한 경우>
<가우스의 방법으로 시간복잡도를 구한 경우>
'자료구조와 알고리즘 > 알고리즘(학부과정)' 카테고리의 다른 글
| 그래프 - Graph(0. Introduction / 1. what is graph?) (0) | 2021.12.07 |
|---|---|
| 4. 그래프 (0) | 2021.11.09 |
| 분할정복 - Divide and Conquer (3.1 Recurrence relation) (0) | 2021.10.05 |
| 분할정복 - Divide and Conquer (3.0 Introduction) (0) | 2021.10.04 |
| 1. STL (0) | 2021.09.02 |