재귀 수식의 시간 복잡도 찾기

Question

저는 재귀 수식의 시간 복잡성 (big O)을 찾으려고합니다.

Answer 1

브레너 (Brenner)가 말했듯이, 당신의 마지막 가정은 거짓입니다. (n 대신 x의 사용)의이 Wikipedia page에서 O(n)의 정의를 보자 :

f(n) = O(n) 경우와 상수 c가 존재하는 경우에만, n0 s.t. 여기에 왜 |f(n)| <= c |g(n)|, 모두 n >= n0에 해당합니다.

O(2^n^2) = O(2^n)을 확인하고 싶습니다. 분명히 2^n^2은 O(2^n^2)에 있으므로 f(n) = 2^n^2을 선택하고 에 있는지 확인하십시오.위의 공식에이 넣어 :

exists c, n0: 2^n^2 <= c * 2^n for all n >= n0

우리가 적절한 상수 값 n0 및 c을 찾을 수 있는지 보자되는 위의 사실이다, 또는 우리가 증거에 모순을 도출 할 수 있다면 그것이 사실이 아니라고 :

양쪽에 로그를 가지고 :

log(2^n^2) <= log(c * 2^n)

단순화를 :

log(2)에 의해

2 ^n log(2) <= log(c) + n * log(2)

나누기 :

n^2 <= log(c)/log(2) * n

더 c이 없다는 것을 알고 쉽게 알, 위에서 모든 n >= n0 마찬가지입니다 n0하는, 따라서 O(2^n^2) = O(n^2) 유효한 가정이 아니다.

Answer 2

당신이 물음표로 지정한 마지막으로 가정이 거짓 :

는 당신이 아래의 식을 내 솔루션을 볼 수 있습니다, 해결책을 찾기 위해 노력했다! 그러한 가정을하지 마십시오.

나머지 조작은 정확합니다. 그러나 그들은 실제로 당신을 아무 곳에도 데려 오지 않습니다.

당신은 초안의 중간에이 연습을 완료해야합니다

T(n) = O(T(1)^(3^log2(n))) 

그리고 바로 그거야. 그게 해결책이야!

당신은 실제로

3^log2(n) == n^log2(3) ==~ n^1.585 

다음은 당신이 얻을 것을 주장 할 수 :

당신이 초안의 두 번째 부분에 만들어 놓은 조작 다소 유사하다

T(n) = O(T(1)^(n^1.585)) 

. 이렇게 남겨 둘 수도 있습니다. 하지만 당신은 지수를 망칠 수 없습니다. 지수의 값을 변경하면 big-O 분류가 변경됩니다.