되풀이 관계를 개발하는 방법을 이해하는 데 어려움이 있습니다. 내가 주어진 해요 코드는 내가 이해가시간 복잡도 및 되풀이 관계
T(n) = n + 1
T(1) = 1
입니다 해요 바로는
int result = bizarre(n, n);
public static int bizarre (int first, int second)
{
if (second <= 1)
{
int temp = 0;
for (int i = 0; i < first; i++)
temp += i;
return temp;
}
return bizarre (first, second-1);
}
하지만 그것은 바로 보이지 않는다. 누군가 나를 도울 수 있습니까? 일반적으로
난 당신이 여기에 문제가 발생하는 이유 중 하나는 당신의 점화식이를 설명하는 두 가지 인수가 필요합니다, 그래서 함수에 두 개의 독립적 인 매개 변수가 있다는 것을 생각합니다.
두 번째 인수가 0 또는 1 인 경우 첫 번째 인수에 비례하여 작업합니다. 이것을
T (m, 1) = Θ (m)으로 쓸 수 있습니다.
그렇지 않으면이 함수는 일정한 작업량을 수행 한 다음 동일한 첫 번째 입력과 감소 된 두 번째 입력에 대해 재귀 호출을합니다. 다음은이 모양입니다.
T (m, n) = T (m, n - 1) + O (1).
거기에서 문제를 해결할 수 있다고 생각하십니까?
이 재발 관계는 당신의 예에서
T(n) = no. of subproblems generated at each step * T(size of each subproblem) + complexity of the divide/conquer step
및
T(1) = complexity of base case(s)
에 의해 주어진다 변수 "두 번째는"각 재귀 호출에서 1로 작아지고있다. 또한 모든 단계에서 생성하는 하위 문제의 수는 메서드를 한 번만 호출하기 때문에 하나뿐입니다.
코드는 비교를 제외하고 각각의 재귀 단계에서 실제로 작동하지 않으므로 O (1) 연산입니다. 그래서
,
T(n) = T(n - 1) + O(1)
T(1) = O(n)
그래, 두 매개 변수가 나를 혼란스럽게 만들었고 이런 식으로 관계를 작성했는지 여부는 확실하지 않았습니다. 재발 사례는 어떻게 얻었는지 이해하지만 기본 사례에 대해 설명해 주시겠습니까? 나는 내 머리를 감싸고있는 것처럼 보일 수 없다. 또한 시간 복잡성에 대해 어떻게 생각하십니까? 비슷한 질문을 한 적은 없기 때문에 사과해야합니다. – Saff
기본 경우에는 O (1) 작업을 각각 수행하면서 '첫 번째'시간을 실행하는 루프 만 있습니다. * m *으로 첫 번째 매개 변수를 나타 냈으므로 수행 된 작업은 O (m)입니다. – templatetypedef
감사합니다. 나에게 약간의 혼란을 주었던 마지막 질문은 기괴한 매개 변수가 모두 'n'인 첫 번째 줄이었습니다. 첫 번째와 두 번째가 기본 경우가 T (1,1) = O가되는 동일한 값임을 의미하지는 않습니까? 1) ? – Saff