알고리즘 : 나누기 및 정복 알고리즘의 재귀 방정식 찾기

A1은 크기N/4 4 서브 문제, 크기N에 문제 나눈다. 그런 다음 이 그들을 해결하고 12n 시간에 대한 해결책을으로 작성하십시오.

어떻게 알고리즘의 런타임을 제공하는 재귀 수식을 작성할 수 있습니까? 질문

당신은 이런 식으로 작성해야 "어떻게 알고리즘의 실행 시간을주는 재귀 방정식을 쓸 수 있습니다"응답

https://en.wikipedia.org/wiki/Master_theorem – Elisha

확인하고, 문제가 발생할 어디입니까? –

@PaulHankin 내 질문을 편집했습니다. –

: T는 (n)은 입력 크기에 대한 알고리즘의 실행 시간을 표시하자 T (n) = 4 * T (n/4) + 12 * n; 최상의 설명

2017-03-27 06:32:55 Swati

되풀이 관계에 의해 주어진다 :

T(n)=4*T(n/4)+12*n

어디에 크기 N, 4 = 하위 문제없이, n/4 각각의 하위 문제 = 크기의 입력에 소정의 알고리즘의 실행 시간 = T(n).

마스터 정리 시간 복잡성을 사용하여

가로 계산됩니다 : theta(n*log n)

2017-03-27 17:27:59

답변