Homogeneous Linear
Homogeneous 는 right value가 0임을 나타내는 것
Linear는 선형적이라는 말
위와 같은 식을
이와 같게 만들어야 한다.
이를 선형식에 대한 특성 방정식 (charateristic equation)이라한다.
k차 방정식은 k개의 근을 가진다.
- 모두가 서로 다른경우(The equation has k distinct roots)
- 중근인 경우 ( multiplicity m >1)
1. 방정식이 k개의 서로 다른 근을 가질때
이와 같은 해를 가지게 된다.
2.모든 근들이 서로 다르진 않은경우 (중근을 가진 경우 == multiplicity m >1)
서로 같은 근은 1. 과 같이 더해준다 그러나 중근인경우는 빨간색 글처럼 추가해준다.
Homogeneous Linear 의 예시1
이를 homogeneous형태로 항을 이동한다.
이를 특성 방정식을 이용해 풀면 아래와 같게 나온다.
r1= 2 이고 r2= -1 으로 서로 다르다. 그렇기에 일반해는 다음과 같이 나온다.
따라서 tn은 아래와 같이 구할 수 있게 된다.
Homogeneous Linear 의 예시2
중근인 경우는 항앞에 n관련 식을 넣어주는 것을 잊지 않도록 한다.
핵심 포인트
tn을 r의 n승으로 바꾸어 수를 넣고 방정식을 만드는 특성 방정식이다.
이를 통해 r의 값을 구하고 외운 식을 이용하여 c의 값을 구하고 최종적으로 tn의 값을 구해야한다.
Nonhomogeneous Linear
원래 식대로 right value를 0으로두고부분을 r-b의 d+1제곱으로 표현하여 식을 완성된다.(
**외울것**)
우선
이렇게 구분하고 서로 다른 k개의 근을 가진다고 한다면
A의 해와 B의 해를 구할 수있다면
tn = t1 + t2라는 해를 얻을수 있다 이를 통해
또다른 방식은
가정1. b와 c가 다름 (같다면 하나로 표기)
Nonhomogeneous Linear의 일반해 예시
n대신 k 와 k-1의 형태로 해보자
T는 복잡도함수로 다음과 같이나타나게 함
그럼 n에 대한식을 T의 관련된 식으로 나타내게 할 수 있음
특성 방정식을 다시 쓰게 되면
이와 같게 됨 이를 이용해서
제일 높은 차수는 nlogn 이다. 따라서 MergeSort의 최악의 경우 시간복잡도는 nlogn이다.
QuickSort
적분을 통해 값을 구해본다.
MergeSort와 ExchangeSort의 비교
n값이 작을때는 MergeSort가 ExchangeSort보다 시간이 많이 걸린다(반나누고 합치고 복잡하기 때문) 더 빨라질때는 어떤 때인가?
t값보다 작아질때는 ExchangeSort를 많을때는 MergeSort를 호출해보자
두개의 값이 같아지도록 정리.
n대신의 t를 써 그럼
알파값이 주어질 때 를 알아봤다.
Divide & Conquer 가 좋지 않을 경우
1. 쪼개진 크기가 원래 크기와 거의 비슷한 경우
2. 쪼개진 크기를 갖는 인스턴스의 수가 원래와 비슷한경우
예시 1
예시 2
크기가 n인 인스턴스를 분할하는데 결국 n/c이긴해도 그 수가 n과 비슷할때
작은 크기로 쪼개지지만 원래와 비슷한 수인경우.
f(n)이 무시할정도로 작아서 전체에 영향을 안준다고 가정
그럼 T(n)의 관련식을 중점으로 문제를 푼다.
가정하기를 n = C의 k승이라 하면
