1
나는 MIT의 오픈 코스웨어 웹 사이트에서 어떤 동영상 강의를 볼 수 있었고, 세 번째 강의 동영상을 강사는 재귀 행렬 곱셈 넘어와 시간 복잡도의 존재와 함께 제공 :스승의 방법, 어떤 경우?
T(n) = Θ(n3)
그것은 나에게 분명 실제로 수학의 일부를 복습 할 필요가 있지만, 저는 그 답과 Master Theorem Method에 대해 언급 된 사례 중 어느 하나와 연결되어 있지 않습니다. 나는 재귀 관계의 형식 것을 알고 :
이 재귀 관계와 N> 1.
에 대한 T(n) = a*T(n/b) + f(n) : a = 8, b = 2 및 f(n) = Θ(n2).
그래서 그들은 어떻게 얻었습니까 Θ(n3)?
그는 log28 = 3을 언급했습니다. 이는 의미가 있습니다. 그러나이 예제의 재귀 관계가 어느 경우에 f(n)의 값을 사용 하는지를 알 수는 없습니다.
사례 2가 f(n) = Θ(anything) 인 유일한 사례이므로, 그 것만 같아요. 그러나, 내 문제는 로그 또는 지수의 속성과 관련이 있다고 생각합니다.
f(n) = Θ(nlog28 * (log2n)k+1) 인 경우 f(n) ~ Θ(n2)의 경우 Θ(n3)에서 케이스 2를 사용하면 어떻게됩니까? 내가 여기서 누락 된 부분은 무엇일까요?
감사합니다. 당신의 답을 읽기 전에, 나는 비디오를 켜 놓고 케이스 1에서 나온 것을 발견했습니다. 당신의 답과 비슷하게, 저는 Theta가 큰 Omicron 안에 여전히 적합하다고 생각했습니다. 왜냐하면 f (n) <= c * g n (n) = O (n)에 대한 조건. 따라서 Theta (n)의 정렬은 f (n) = c * g (n)을 의미하므로 O (n) 내에 여전히 적합합니다. –