여기서 대체 방법을 사용하여 반복 관계를 해결하는 방법을 살펴보겠습니다. 더 나은 방법으로 이해하기 위해 두 가지 예를 들어보겠습니다.
이진 검색 기술을 사용한다고 가정합니다. 이 기술에서는 요소가 끝에 있는지 여부를 확인합니다. 그것이 중간에 있으면 알고리즘이 종료되고, 그렇지 않으면 실제 배열에서 왼쪽 및 오른쪽 하위 배열을 계속해서 가져옵니다. 따라서 각 단계에서 배열의 크기는 n / 2만큼 감소합니다. 이진 검색 알고리즘을 실행하는 데 T(n) 시간이 걸린다고 가정합니다. 기본 조건은 O(1) 시간이 걸립니다. 따라서 재귀 방정식은 다음과 같습니다. -
$$T(n)=\begin{cases}T(1) &for\:n \leq 1\\2T(\frac{n}{2})+c &for\:n> 1\end{cases }$$
해결 - 결과를 얻기 위해 각 단계의 공식을 대체할 것입니다 -
$$T(n)=T(\frac{n}{2})+c$$
T(N/2)를 대체하여 다음과 같이 쓸 수 있습니다.
$$T(n)=(T(\frac{n}{4})+c)+c$$
$$T(n)=T(\frac{n}{4})+2c$$
$$T(n)=T(\frac{n}{8})+3c$$
$$T(n)=T(\frac{n}{2^{k}})+kc$$
이제 $$(\frac{n}{2^{k}})$$가 1에 도달하면 2 k n이다. 따라서 k의 값은 log2입니다. 𝑛
T(n)의 복잡성 =ϴ(log n)
마찬가지로 병합 정렬과 같은 다른 예를 선택하면 목록을 두 부분으로 나눕니다. 이 분할은 목록 크기가 1이 될 때까지 발생합니다. 그런 다음 정렬된 순서로 병합합니다. 병합 알고리즘은 O(n) 시간이 걸립니다. 따라서 병합 정렬 알고리즘에 T(n) 시간이 걸리면 이를 두 개의 반으로 나누고 각각에 대해 동일한 작업을 수행하면 T(n/2) 등이 소요됩니다. 따라서 반복 관계는 아래와 같을 것입니다 -
$$T(n)=\begin{cases}T(1) &for\:n =1\\2T(\frac{n}{2})+cn &for\:n> 1\end{cases} $$
해결 - 결과를 얻기 위해 각 단계의 공식을 대체할 것입니다 -
$$T(n)=2T(\frac{n}{2})+cn$$
T(N/2)를 대체하여 다음과 같이 쓸 수 있습니다.
$$T(n)=2(2T(\frac{n}{4})+\frac{cn}{2}) +cn$$
$$T(n)=4T(\frac{n}{4}) +2cn$$
$$T(n)=8T(\frac{n}{8}) +3cn$$
$$T(n)=2^{k}T(\frac{n}{2^{k}}) +kcn$$
이제 $$(\frac{n}{2^{k}})$$가 1에 도달하면 2 k n이다. 따라서 k의 값은 log2입니다. 𝑛. 그리고 T(n)은 -
가 될 것입니다.𝑇(𝑛) =𝑛𝑇(1) + 𝑐𝑛 로그2 𝑛
복잡도는 θ(n log n)