저는 올바른 방향으로 가고 있는지 확인하고 싶었습니다. 나는 배열의 최대 값을 재귀 적으로 분할하여 각 개별 배열의 최대 값을 찾아서 찾고 싶다. 나는 그것을 분할하기 때문에 2 * T (n/2)가 될 것입니다. 그리고 내가 2 개의 배열에 대한 비교를해야하기 때문에 T (1)이 있습니다. 그래서 내 점화식은 다음과 같이 될 것이다 :최대 재귀 적으로 찾는 시간 복잡도는 무엇입니까
T = {2 × T (N/2) + 1 일 때, N> = 2, T (1)의 경우, N = 1;
따라서 제 복잡성은 Theta (nlgn)입니까?
작성한 수식이 맞지만 분석이 완벽하지 않습니다. i 번째 반복에 대한
T = 2*T(n/2) + 1 = 2*(2*T(n/4) + 1) + 1 = ...
당신은 얻을 것이다 :
Ti(n) = 2^i*T(n/2^i) + i
을 이제 내가/2^난 동일 하나 (또는 어떤 일정에 대해, 만약 N 않는 알고 싶은 당신이 좋아하기 때문에) n = 1의 최종 조건에 도달합니다. 그것은 n/2^I = 1 -> I = Log2 (n)에 대한 해답이 될 것입니다.
TI(n) = 2^log2(n)*T(n/2^log2(n)) + log2(n) = n*1+log2(n) = n + log2(n)
당신은 T (N) = O (N + N은 log2() (@bdares 말한 것처럼) = O (n)이 (처럼 얻을 @ 티의 방정식에 공장을 당신은 얻을 badares가 말했다)
아니요, 아니요 ... 각 재귀마다 O (1) 시간이 걸립니다.
몇 개가 있습니까?
N 잎이있어 적어도 O (N)임을 알 수 있습니다.
절대 최대 값을 찾기 위해 몇 명을 비교해야합니까? 그건 O (log (N))입니다.
함께 추가하십시오. 곱하지 마십시오. O (N + log (N))는 시간 복잡성입니다.
해명 해 주셔서 감사합니다 – Dan
O (n + log (n))을 쓰는 것이 정상입니까? 모든 이벤트에서 O (n)가 충분할 것 같습니다. 사실, 왜 그렇게 부드럽게 구워? 나는 O (n + log (n))을 쓰는 것 같은 느낌이 들지만 바보 같지는 않다. 우리는 Bubblesort에 O (n^2 + n)을 쓰지 않습니다. 내가 놓친 게 있니? 단지 설명 목적으로 사용한다면 OK입니다. 내게 마지막 단계가 수행되지 않는다는 사실이 좀 이상하다고 생각합니다. 그렇다면이 내용을 콘텐츠가 아닌 스타일을 비판하는 것으로 받아들입니다. – Patrick87
@bdares 네가 맞아. 나는 마지막 단계를 더해야했다. 혼란을 피하기 위해 이것을 설명 할 때 (n + log (n)) 부분을 건너 뛰는 것을 피하지만 마지막 부분도 추가해야합니다. – Neowizard