의 실행 시간은 다음 해결책이 맞는지 누구에게 말해 줄 수 있습니까?t (n) = t (n-2) + (n-2) ²
I은 (n)은 t = t의 실행 시간을 계산하는 것을 시도하고있다 (N-2) + (N-2) ²
는 N (상기
=> t 그것을 평가 (n-6) + (n-6) ² + (n-2) ² (n-4) + t (n-4) + n²
... 2로 줄이면되기 때문에 ND N/2의 조건과 모든 사각형 확장함으로써 우리가 (N/2) * 상기 실행 시간 n³.So 같음 (n²)입니다 세타 (n³)
이 올바른 해결책 ?
예, 위의 내용은 완전히 정확합니다. 첫 번째 줄의 작은 부분은 문제 정의에 따라 t(n) = t(n-4) + (n-4)^2 + (n-2)^2이어야하며 뒤 따르는 내용은 수정해야합니다. 그러나 점근 적 결과에는 영향을주지 않습니다.
이것을 증명하기 위해, 우리는 mathematical induction을 사용할 수 있습니다 : 모든 남아
Claim: t(n) <= n^3
base: T(2) = 2 (assumption - otherwise we'll get stuck)
let's assume the assumption is true for each n<k for a certain k.
t(k) = t(k-2) + (k-2)^2 <= (k-2)^3 + (k-2)^2 =
= k^3 -6k^2 + 12k -8 + k^2 - 4k + 4
= k^3 -5k^2 + 8k - 4
우리가 완료 5k^2 >= 8k - 4 있고 보여주는 것입니다. 방정식은 각 k>=2에 대해 유지됩니다.
위에서 t (n)은 O(n^3)에 있습니다. 우리가 볼 수있는 유사한 접근법을 사용하면 Omega(n^3)이기도하므로 Theta(n^3)
'k^3 -5k^2 + 8k + 4'는 실제로'k^3 -5k^2 + 8k - 4'가되어야합니다. 결론은 물론 각각의 k> = 2에 대한 공식은 여전히 유효합니다. – amit
어디 보입니까? 비 동시성 실행 시간을 얻으려면 프로 버전이 필요합니까? –
@TheUnfunCat이 포스트 업데이트를 보았습니다 – FLCL
more이 질문은 computerscience.stackexchange.com의 문제입니다. –
해당 기능의 실행 시간을 계산 하시겠습니까? 나는. 그 기능을 컴퓨터 프로그램으로 구현한다면 실행 시간이 무엇인지 알고 싶습니까? 아니면 당신이 그 기능 *이 당신의 러닝 타임이고 당신이 어떤 O에 있는지 알고 싶습니까? – sepp2k
예 기능의 실행 시간을 계산하려고합니다. (기능 순서) – Sid