왜 재발 알고리즘

Question

질문

로 대체 T (1) 내가 알고리즘의 복잡성을 찾기 위해 노력하고있을 때 우리는 큰-O를 추론 할 수 있습니다. 알고리즘은 반복적 크기N-1 두 하위 문제를 해결 한 후 일정 시간 과 용액을 결합하여 크기 N의 문제를 해결한다. 그러므로 내가 구글에 대한 몇 가지 검색을 수행

T(n) = 2 * T(n-1) + 1 * O(1) 
    = 4 * T(n-2) + 3 * O(1) 
    = 8 * T(n-3) + 7 * O(1) 
    = 2^k * T(n-k) + ((2^k)-1) * O(1) 

나는이 시점에서 붙어 :

그래서, 나는 재발 물품. 대부분의 예 T (N-K)가T (1)된다 있도록 N-1로K 대체. 그 후

T(n) = 2^(n-1) * T(1) + ((2^(n-1))-1) * O(1) // substitute k with n - 1 

문제, 그들은이 재발의 큰-O을 체결 O(2^(n-1))입니다.

너무 혼란 스럽습니다. 나도 모르겠다

(i) 나는 아직도 T(1)의 복잡성을 안다. 그렇지 않습니까?

(II) T(1)는 결론에 관련되는 방법 및

(Ⅲ) 우리가 식 T(n) = 2^(n-1) * T(1) + ((2^(n-1))-1) * O(1)에서 큰 O를 찾는 방법.

도움이 될 것입니다.

Answer 1

T(n) = 2^(n-1) * T(1) + ((2^(n-1))-1) * O(1) 

여기서 T (1)은 항상 일정하다. 왜냐하면 T(n)은 k의 큰 값에 대해 입력 크기가 n > k 인 시간 복잡도를 의미합니다. 이제 n이 예를 들어 n = 5과 같이 일정하다면 알고리즘의 시간 복잡도는 일정합니다. n = 5에 대한 알고리즘을 실행하기 때문에 동일한 시간이 걸릴 것입니다.

시간 복잡도에서 우리는 함수의 성장을 측정합니다. 이제 n의 상수 값에 대한 성장은 일정합니다. 이 로직의 경우 T(1) = constant.

이 아이디어는 배열의 중간 값을 찾는 데 사용되었습니다. 이 배열은 배열을 5 개의 요소 덩어리로 나누고 각 덩어리의 정렬은 일정하다고 주장합니다. 크기가 고정되어 있기 때문입니다.