반복 관계 다차원 배열을 재귀적으로 정의하는 방정식입니다.
여기서 우리는 반복 관계를 기반으로 그 문제를 해결할 것입니다.
Solve the recurrence reation:T(n) = 12T(n/2) + 9n2 + 2. T(n) = 12T(n/2) + 9n2 + 2. Here, a = 12 and b = 2 and f(n) = 9(n)2 + 2 It is of the form f(n) = O(n^c), where c = 2
이것은 마스터의 정리 조건에서 형성되며,
So, logb(a) = log2(12) = 3.58 Using case 1 of the masters theorm, T(n) = θ(n3.58).
Solve the recurrence reation:T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3. T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3
단순화하면 큰 값의 경우 n,n/2>> 23이므로 23은 무시됩니다.
T(n) = 5T(n/2) + 5n2 + 7n - 5/3. Further, we can take 5n2 + 7n - 5 ≃0(n2). So, T(n) = 5T(n/2) + O(n2)
이것은 마스터 정리의 경우 2에 해당합니다.
So, T(n) = O(n2).
다음이 어떤 경우에라도 석사의 정리에 해당하는지 확인하십시오.
T(n) = 2T(n/3) + 5n
아니요, 석사 정리를 적용하려면 함수가 다항식 함수여야 합니다.
T(n) = 2T(n/5) + tan(n)
아니요, 삼각 함수는 마스터 정리에 포함되지 않습니다.
T(n) = 5T(n+1) + log(n)
아니요, 대수 함수는 마스터 정리에 포함되지 않습니다.
T(n) = T(n-7) + en
아니요, 지수 함수는 마스터 정리에 포함되지 않습니다.
T(n) = 9n(n/2+1 ) + 4(n2) - 17 Yes, as solved above.