나는 지난 10 월 생물 정보학에서 석사 학위를 시작했습니다. 전 생물 학자가 코드 조각에서 재귀 방정식을 찾는 것이 꽤 어렵 기 때문입니다. 누군가가이 사실을 설명 할 수 있다면 매우 감사 할 것입니다.알고리즘의 회귀 방정식
이 코드 부분에서 재귀 방정식을 어떻게 찾을 수 있습니까?
procedure DC(n)
if n<1 then return
for i <- 1 to 8 do DC(n/2)
for i <- 1 to n³ do dummy <- 0
제 추측 따라서 상태가 일정 시간 (C) 1 내지 8 행하는 재귀 경우는 루프에 대한 제를 필요로하는 경우 제 때문에 8T (N/2), T (N) = C를 +이고 8 * T (n/2),하지만 내 방정식에 코드의 마지막 줄을 광고하는 방법을 모르겠다.
당신은 가깝지만, 그게 아닙니다.
일반적으로 반복 관계는 기본 사례가 일정한 양의 작업을한다고 가정하기 때문에 재귀 프로 시저의 재귀 단계에서 수행되는 작업 만 설명합니다. 그러므로 당신은 그들이에 만든하는지 크기 입력 만들어에있는 재귀 무엇을 호출
정확하게 n/2 크기의 입력에 8 개의 재귀 호출이 있음을 확인 했으므로 8T (n/2) 용어가 정확합니다. 그러나 이것이 O (n)가 작동하는 루프가 뒤 따른다는 것을 알아 두십시오. 따라서, 재귀 기능은 더 정확하게
로T (n)를 모델링 8T = (N/2) + O (N 3).
이 재발 O (N 3 로그 N)에 해결 이유를 주장 할 수 있다면 그것은보고 후 가치가있다.
내가 시작했을 때 당신이 썼다 ... :) 나는 느린 총이다. – coderredoc
이것은 T(n)= 8*T(n/2)+O(n^3)으로 밝혀졌습니다.
나는 iteration/recursion tree 방법으로 이것을 해결하는 잽을 줄 것이다.
T(n) = 8* T(n/2) + O(n^3)
~ 8* T(n/2) + n^3
= 8*(8* T(n/4) + (n/2)^3))+n^3
= 8^2*T(n/4)+8*(n/2)^3+ n^3
= 8^2*T(n/2^2)+n^3+n^3
= 8^2(8*T(n/8)+(n/4)^3)+n^3+n^3
= 8^3*T(n/2^3)+ n^3 + n^3 + n^3
...
= 8^k*T(n/2^k)+ n^3 + n^3 + n^3 + ...k time ...+n^3
n/2^k=1 or k=log_2(n) 때 중지됩니다.
그래서 복잡도는 O(n^3log(n))
입니다. –
@Peet .:'1 - 1' 또는 다른 어떤 것입니까? – coderredoc
나는 이것이 당신의 질문에서 분명하지 않다고 생각합니다. 재귀 적 표기법을 사용하여 시간 복잡도를 설명해야합니다. 나는 언어가 직관적 인 의사 코드라고 생각한다. – storaged