1 부터 10까지 더하는 것 => 행렬 => 팩토리얼
기존의 팩토리얼 재귀 함수는 아래와 같이 선형 알고리즘이었다!
// 함수(변수) => 변수가 1이 될때까지 계속 뺌
static int 팩토리얼(int n) {
// 변수가 1이 되면 1을 반환함
if(n==1)return 1;
// 10 > 9 > 8 > 7 > 6 > 5 > 4 > 3 > 2 > 1 (if문에서 return 1) 반환!
// 반환중 1 > 2+1 > 3+3 > 4+6 > 5+10 > 6+15 > 7+21 > 8+28 > 9+36 > 10 + 45 반환 완료
// 반환이 끝났다면 아래 return 문으로 (45) + 10 을 반환한다!
return 팩토리얼 (n-1) + n;
}
하지만 위와 같은 코드보다 더욱 효과적으로 작성할수 있는 방법이 책여 쓰여있었다!
책에서는 수학 공식으로 설명을 해주었는데 필자는 예체능 원툴에 현재 개발 공부 6개월이다!
(로그 , 사인 , 코사인 , 행렬 , 조합이 무엇인지조차 배우지 못했따... 그래서 수학도 공부하고 있다!!)
1부터 n의 합을 절반으로 나눈다면 어떻게 될까!
(1 + 2 + 3 + ~ ~ ~ ~ n/2 ) + (n/2 + 1 + ~~~~~~ n) 처럼 절반으로 일단 나눈다!
각 부분 문제를 1부터 n까지의 합의 꼴으로 표현해야하는데 두번째 조각은 a부터 b의 합을 가지고 있기 때문에
두번째 부분 문제를 조금 수정하여야 한다!!
n/2 * n/2 + (1+2+3 ~~~~ n/2) 으로 바꾸면
결국 n/2 * n/2 + fast(n/2)가 된다!! 이것이 아래 함수의 return 값이 될것이다!
static int fast (int n) {
// 기저 조건은 동일하다!
if(n == 1) return 1;
// 하지만 n을 2로 나누었을 때 == 홀수 라면
// 이전값 짝수를 재귀한 값 + 현재 값 을 더한다!
if(n%2 == 1) return fast(n-1) + n;
// 반환값은 어떠한 수학 식으로 인해 이렇다고한다!
return 2 * fast (n/2) + (n/2) * (n/2);
}
시간 복잡도는 원래라면 선형 시간 O(n)이지만
분할탐색을 이용하여 빠르게 구하는 알고리즘은 값을 구할 때 절반으로 나누며 값을 구하기 때문에
O(log N) 이 된다! 쉽게 이해하기 위해 절반정도 걸린다고 이해했다!
행렬의 거듭제곱을 계산하기 위해서는 O(n^3) 의 시간이 걸린다!
그리고 곧이곧대로 구하게 된다면 O(n^3 * m) 이 되며 n이 100 이고 m 이 1,000,000 이라면
필요한 연산 수가 1조가 된다고한다! (1조란 단군시대때부터 월 60만원씩 매일 써도...)
위의 빠른 알고리즘을 이용하여 조각을 또 나누어볼거다!
A^m - A^m/2 * A^m/2 => 수학적으로는 이해가 안됐지만 문제를 절반으로 나눈 뒤 and연산으로 합친 거로 이해했다!
신기한게 수학적으로는 이해가 100% 되진 않았지만 코드 구현은 했네..? 어케했지
일단 여러번 돌려본 결과 맞는거 같긴한데 자신이 없다! 혹시 틀렸다면 알려주면 고맙습니다 !
// 두가지 클래스를 쓴다!
// 변수를 그냥 제곱해주는 클래스이다!
static Long identity(int n) {
return (long) Math.pow(squareMatrix, n);
}
// A^n => pow (A , n) 으로 이해하면 될듯 하다!
static Long pow ( Long squareMatrix , int m) {
// 지수가 0이라면 a의 길이를 넘겨 거듭제곱한다!
if(m == 0) return identity(squareMatrix.SIZE);
// 지수가 홀수라면 지수를 짝수로 만든 값과 현재 값을 곱해준다!
if(m%2 > 0) return pow(squareMatrix , m-1) * squareMatrix;
// 그리고 n/2 승을 만들어준다!
Long half = pow(squareMatrix, m/2);
// A^m = A^m/2 & A^m2 식으로 만들어주기 위해 half를 곱해준다!
return half * half;
}
다음은 병합 정렬과 퀵 정렬로 돌아오겠다!