:Big Theta에서 c1을 찾는 방법은 무엇입니까? 우리는 다항식이 가지고있는 경우
f(n) = 8n^2 - 4n + 2
우리는 다음 g (N)를해야합니다 =
BigTheta(f(n)) = 0 <= c1g(n) <= f(n) <= c2g(n), n > n0
이 나는 것을 찾을 수 C2를 알고^N, 우리는 추가 할 모든 계수 : 8 - 4 + 2 그러므로 c2 = 2, 맞습니까? 그러나 c1은 어떨까요? c1은 항상 1과 같습니까? 아니면 항상 가장 작은 양의 계수와 동일할까요? 여기에 일반적인 규칙은 무엇입니까? 우리가있는 경우
또 다른 예를 들어, :
f(n) = 9n^2 + 3n/2 + 1/4
g(n) = n^2
는 그 C2 알고 = 10.75 그러나 = 1 또는 1/4 C1 것인가?
나는 단단한 경계를주는 c1을 이해하는 일반적인 규칙을 찾고 있습니다.
대단히 감사합니다.
"항상"무엇이 될지 말하기 어렵습니다. 그러나 예를 들어, 8n^2 - 4n + 2는 항상 4n^2만큼 크므로 c1을 4 (또는 더 작은 것 : 1, 2 또는 3)로 선택할 수 있습니다. 어떻게 알았어? 음, 우리는 f1 (n)보다 작은 c1n^2 형태의 함수를 원합니다; 8n^2는 8n^2 + 2보다 작습니다 (즉, 추가되는 항을 무시할 수 있습니다). 그러나 -4n 항에 대해 걱정해야합니다. 그래서, 가장 간단한 방법은 4n이 4n^2보다 작기 때문에 8n^2 - 4n^2가 8n^2 - 4n + 2보다 작을 것입니다 (왜냐하면 나는 더 큰 것을 빼기 때문입니다). 따라서
4N^2 = 8N^2 - 4 N^2 < = 8N^2 - 4N < = 8N^2 - 4N + 2 < = F (N)
정도로는 C1 내지 동일 선택할 수 4.
이러한 문제에는 단 하나의 정답이 없습니다. 당신은 당신이 보여줄 수있는 상수가 f1 (n)보다 더 작게 만들 필요가 있습니다.
두 번째 예에서는 모든 용어를 추가 했으므로 삭제하십시오. 9n^2 < = 9n^2 + 3n/2 + 1/4이므로 c_1 = 9를 선택하십시오. 일반적인 알고리즘으로 가정하면 가장 큰 차수의 계수를 빼고 모든 음의 계수를 뺄 수 있습니다 (무시하고 무시하십시오). 긍정적 인 것). 그것은 긍정적 인 가치를 얻는다는 가정하에 올바른 답을 줄 것입니다. 그렇지 않다면 n0로 바이올린을하거나 c1을 1보다 작은 부분으로 만들어야합니다.