알고리즘을 분석하는 동안 몇 가지 반복 관계를 찾습니다. 이러한 반복 관계는 기본적으로 표현식에서 동일한 기능을 사용합니다. 재귀 알고리즘 분석과 분할 정복 알고리즘의 경우 대부분의 경우 재귀 관계를 얻습니다.
여기에서 몇 가지 예의 도움으로 반복 방정식의 한 예를 볼 것입니다. 이진 검색 기술을 사용한다고 가정합니다. 이 기술에서는 요소가 끝에 있는지 여부를 확인합니다. 그것이 중간에 있으면 알고리즘이 종료되고, 그렇지 않으면 실제 배열에서 왼쪽 및 오른쪽 하위 배열을 계속해서 가져옵니다. 따라서 각 단계에서 배열의 크기는 n / 2만큼 감소합니다. 이진 검색 알고리즘을 실행하는 데 T(n) 시간이 걸린다고 가정합니다. 기본 조건은 O(1) 시간이 걸립니다. 따라서 재귀 방정식은 아래와 같을 것입니다 -
$$T(n)=\begin{cases}T(1) &for\:n \leq 1\\T(|\frac{n}{2}\rvert)+c &for\:n> 1\ 끝{케이스}$$
마찬가지로 병합 정렬과 같은 다른 예를 선택하면 목록을 두 부분으로 나눕니다. 이 분할은 목록 크기가 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} $$
우리는 대체, 반복 트리 방법과 같은 다른 방법을 사용하여 이러한 방정식을 풀 수 있으며 마스터 방법을 사용하여 특별한 종류의 반복 관계를 풀 수 있습니다.