- 정의
- 합 배열을 이용해 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
- 합 배열
- S[i] = A[0] + A[1] + A[2]+ ... + A][i]를 통해 미리 합을 구해 배열에 저장해 놓는 것
- 합 배열을 미리 구하면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(n)에서 O(1)이 된다
'자료구조 > Do It' 카테고리의 다른 글
| 선택 정렬 (0) | 2023.10.26 |
|---|---|
| 버블 정렬 (0) | 2023.10.25 |
| 스택과 큐 (0) | 2023.10.24 |
| 배열과 리스트 그리고 벡터 (0) | 2023.10.20 |
| 시간 복잡도 (0) | 2023.10.20 |