반복 관계를 사용하여 알고리즘 시간 복잡도

반복 관계를 사용하여 시간 복잡도를 분석하는 데 대한 두 가지 질문이 있습니다.반복 관계를 사용하여 알고리즘 시간 복잡도

질문 1. 메모 작성을 사용할 때 알고리즘의 반복 관계를 구성하는 방법은 무엇입니까? 이것은 가능한가?

예를 들어 피보나치 시퀀스의 n 번째 항을 계산하는 것을 고려하십시오. 알고리즘이 될 것이다 :

fib(n) 
    if n < 2 
     return n 
    else 
     return fib(n-1)+fib(n-2)

이런 코드의 점화식은 다음

T (N) = T (N-1) + T (N-2) + (C). 이 시간 복잡도는 대략 2^n입니다.

이 코드의 memoized 버전은 다음과 같습니다

이

MemFib(n) 
    if n < 2 
     return n 
    else 
     if F[n] is undefined 
      F[n] = MemFibo(n − 1) + MemFibo(n − 2) 
     return F[n]

(참고 : 나는 여기에서 찾을 수 있습니다 제프 에릭슨의 노트에서이 나섭니다 : http://jeffe.cs.illinois.edu/teaching/algorithms/이 알고리즘은 5 장에 - 동적 프로그래밍.)

이 복잡도는 O (n)입니다. 우리가 테이블 'F'에 값을 저장하고 가능할 때마다 조회를 수행하기 때문에 이것이 왜 O (n)인지 이해하지만이 것을 수학적으로 증명하는 방법을 모르겠습니다.

지금 당장 제게 반복되는 관계는 분명히 잘못된 첫 번째 예제 (T (n-1) + T (n-2) + c)와 같습니다. 이 재발 관계를 어떻게 써야할까요? 항상 재귀 호출을 수행하지 않기 때문에 관계를 작성할 수 있습니까? 그것이 가능하지 않다면 시간 복잡성을 공식적으로 O (n)이라고 어떻게 증명할 것입니까? 다음과 같은 형식이다 알고리즘의 복잡도 분석하는 방법

질문 2 :

T는 (n)은 T (N/B) + (C) T (N/D를) = + x?

여기에서 x는 상수입니다.

출처

2017-09-22 Ar254

질문 2에 답하려면 이전 답변 [https://stackoverflow.com/questions/45424921/tn-c1t]이 필요합니다. n-a-c2t-b-fn/45425519 # 45425519). 1 번 질문에 대한 힌트로서, 두 번째 재귀 호출은 배열의 앞이나 뒤에 채워지기 때문에 항상 일정 시간입니다 (단, 호출 순서는 많은 프로그래밍 언어에서 정의되지 않습니다) – meowgoesthedog

첫 번째 질문의 경우 T (n)이 이미 호출되었는지 여부 (O (n) 또는 O (1))에 따라 두 개의 값이있을 수 있으므로 반복 관계는 더 이상 true가 아닙니다.

제 1 및 제 2 호 차별화하는 것이 재발을 작성하는 방법 : 특정 예에서

: 두 번째 질문를 들어

Tf(n) = Tf(n-1) + Ts(n-2) + c = Tf(n-1) + O(1) + c = O(n).

, 마스터 정리를 확장 할 수 있습니다 x = O (1) :

T(n) = θ(n^γ) with γ such as a*(1/b)^γ + c*(1/d)^γ = 1

출처

2017-09-22 09:04:32 user1470500

반복 관계를 사용하여 알고리즘 시간 복잡도

답변

관련 문제