728x90
반응형
곱셈 계산의 속도를 높이기 위해 고안된 카라츠바 알고리즘에 대해 보던 중 시간 복잡도를 구하는 과정에서 로그의 성질에 대해 정말 오랜만에 찾아보게 되었다.
카라츠바 알고리즘은 위키피디아에 나와있다.
카라추바 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 카라추바 알고리즘은 소련의 수학자 아나톨리 알렉세예비치 카라추바가 1960년에 발견하고 1962년에 공개한, 큰 수에 대한 효과적인 곱셈 알고리즘이다. [1][2][3] 이 방법은 두 n자리 수의 곱셈을 최대 3 n log 2 3 ≈ 3 n 1.585 {\displaystyle 3n^{\log _{2}3}\approx 3n^{1.585}} (n이 2의 거듭제곱일 때는 정확하게 n log 2 3 {\displayst
ko.wikipedia.org
고등학교 떄 배우고선 기억이 잘 나지 않았는데 다시 보니깐 그때의 기억이 조금씩 살아났다.
시간 복잡도는 다음과 같았다.
▶(ㄱ)을 등비 급수 공식으로 묶어 내면 (ㄴ)이 된다. 시간 복잡도를 계산할 때 log는 밑이 2인 경우를 기본으로 한다.
▶(ㄴ)에서 위의 항을 뽑아내고 이를 로그의 성질을 이용해 정리해 보고자 한다.
▶밑과 지수에 있는 로그의 밑이 같은 경우의 변환
▶밑과 지수에 있는 로그의 밑이 다른 경우의 변환
두 변환을 바탕으로 복잡도를 간소화 시켜보면,
즉 복잡도는 O(n^log3)이 된다.
728x90
반응형
'study_life' 카테고리의 다른 글
| 선형 대수 관련 용어-선형 연립 방정식 (0) | 2020.04.07 |
|---|---|
| norm(노름) (0) | 2020.03.26 |
| 전처리에 관하여 (0) | 2020.02.11 |
| 단양 여행 (0) | 2020.02.07 |
| 유럽 여행 준비물(여름) (0) | 2019.08.30 |
댓글