답은 무엇입니까? n! = Θ()?

-7

어떻게 대답을 찾을 수 있습니까? 빅 오 (Big O)로도 충분합니다. 제가 발견 한 모든 단서는 복잡한 수학 아이디어입니다. 어떤 도움?답은 무엇입니까? n! = Θ()?

이 문제를 해결하기위한 올바른 접근 방법은 무엇입니까? 재귀 트리가 너무 많은 것처럼 보입니다

목표는 n! 그리고 n^logn

2014-03-25 Alex

어? 'n! = Θ (n!)'이다. "너!"라고 말하는 다른 방법을 찾고 있니? – Sneftel

'O (n!)'는 잘못된 답변입니까? 또한 'O'는 함수의 클래스를 나타내며 그러한 평등은 무의미하기 때문에 함수가 'O'와 같은 것을 실제로 말할 수는 없습니다. 그것은 말하는 것이 더 합리적입니다. – luk32

@ luk32 "="는 매우 일반적으로 사용됩니다. [Wikipedia] (http://en.wikipedia.org/wiki/Big_O_notation) - ""= "는"정상적인 수학적 의미에서 "와 동일하지만 오히려 구어체로 표현됩니다. "". – Dukeling

는 매우 정확하고 유효한 복잡성이므로 n! = Θ(n!)입니다. 니클라스는 지적

,이
6x² + 15x + 2 같은 것을 위해, 당신은 Θ(6x² + 15x + 2)을 쓸 수 있지만, 모든 기능에 대한 사실은 사실이지만, 일반적으로 단순히 대신 Θ(x²)를 작성하는 것이 바람직 할 것이다.

당신은 단순히 WolframAlpha에 음모를 꾸미고, 두 가지 기능을 비교하려면

는 Θ(n!) 기능이 빠르게 성장할 것을보고이 충분히 고려 될 수 있습니다.

수학적 결과를 결정하기 위해, 우리는 우리에게 log (n!) 및 log n^{log n} = log n . log n = (log n)²을 제공, 모두의 log 수 있습니다.

그러면 n에 대해 log(n!) = Θ(n log n) 및 n log n > (log n)²이므로 Θ(n!)이 더 빠르게 성장한다고 알 수 있습니다.

파생어는 아마 사소한 것이지만 실제로 가능한지 여부는 약간 확신 할 수 없지만 좀 더 자세한 내용은 the Mathematics site을 시도하십시오. 아직 스택 오버플로 범위를 벗어납니다.

출처

2014-03-25 17:45:27 Dukeling

사실 모든 함수에 대해 : * f *가 무엇인지에 관계없이'f (n) = Θ (f (n))'을 유지합니다. –

이것은 대답이 아닌 것처럼 느껴집니다. –

@G.바흐 사실은 다소 동의하지만 질문이 무엇을 요구하는지 묻는 동안 이것은 대답입니다 (비록이 질문이 끝나면 나는 특히 짜증스럽게 말할 수는 없지만). 주어진 두 함수를 비교하는 방법을 묻는 질문을 * 변경하려면 [math.se]에 속해 있기 때문에 주제를 벗어난 상태로 닫아야합니다. – Dukeling

"닫힌 양식"표현식을 원한다면 n! = Ω ((sqrt (n/2))^n) 및 n! = O (n^n). 그것들이 더 유용하다는 것을 명심하십시오.

이들을 유도하려면 (n/2)^(n/2) < n! < n^n.

n^(log n)과 비교하려면 제한 규칙을 사용하십시오. 당신은 n = e^(log n)을 사용하기를 원할 수도있다.

출처

2014-03-25 18:19:23

답은 무엇입니까? n! = Θ()?

답변

관련 문제