어떻게 복잡도를 계산할 수 있습니까

Question

내 알고리즘은 항상 n!*4^n 단계를 수행한다는 것을 알았습니다. 나는 그 복잡한 점을 알고 싶습니다 O(n!*4^n) 또는 다른 것입니까? 감사. 당신이 당신의 알고리즘은 항상n!⋅4ⁿ 단계를 을 할 것이라고 확신 경우뿐만 아니라 그것이 Ω(n!⋅4ⁿ)의 같은 Θ(n!⋅4ⁿ)을의로

Answer 1

정확히n!*4^n 개의 단계가있는 경우 큰 오 표기법이 필요하지 않습니다.

그렇습니다. 즉, 복잡성이 O(n!*4^n)입니다.

Answer 2

, 그것은뿐만 아니라 O(n!⋅4ⁿ)을합니다.

Answer 3

이 Θ(n!⋅4ⁿ)이고 Θ이 O에 대한 하한 때문에 그것은 O(n!⋅4ⁿ)는 또한 Ω(n!⋅4ⁿ)의도이다.

그냥 중요한 것은 당신의 단계에서 무엇입니까? 각 단계가 O (1)이면이 표기법이 적용되지만 다른 경우에는 단계에 따라 달라 지므로 함수를 표시하여 단계가 무엇인지 확인하십시오.

그리고 왜 그것이 O(n!)이라고 말할 수 없습니까? 당신은 일정한 찾을 수 없기 때문에 c 같은 그 : 때문에 모든 일정 c 때 4ⁿ > c (대한 예를 들어

N ⋅4ⁿ ≤ c⋅n! N에 대한> n은 0

_{! 때 n ≥ c) 위의 부등식이 잘못되었습니다.}