我如何计算复杂度
我发现我的算法总是执行 n!*4^n
步骤。我想知道它的复杂度是 O(n!*4^n)
还是其他?谢谢。
I have found out that my algorithm will always do n!*4^n
steps . I'd like to know wheter its complexity will be O(n!*4^n)
or will it be something else? Thanks.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
![扫码二维码加入Web技术交流群](/public/img/jiaqun_03.jpg)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
如果您确定您的算法将始终执行
n!⋅4ⁿ
步,那么它的复杂度就是O(n!⋅4ⁿ)
,并且一个θ(n!⋅4ⁿ)
以及一个Ω(n!⋅4ⁿ)
。If you are sure that your algorithm will do always
n!⋅4ⁿ
steps, it's aO(n!⋅4ⁿ)
as well as it's aΘ(n!⋅4ⁿ)
as well as it's aΩ(n!⋅4ⁿ)
.它是
θ(n!⋅4ⁿ)
并且因为θ
是O
的下界,所以它也是O(n!⋅4ⁿ)< /code> 也是
Ω(n!⋅4ⁿ)
。重要的是你在你的步骤中做什么?如果每个步骤都是 O(1) 这个符号成立,但在其他情况下,这取决于你的步骤,我建议向我们展示你的函数,看看步骤是什么。
为什么你不能说它是
O(n!)
?因为你找不到常量c
,这样:因为对于任何常量
c
,当4ⁿ > c
(例如当n ≥ c
时)上述不等式是错误的。It's
Θ(n!⋅4ⁿ)
and becauseΘ
is lower bound forO
it's alsoO(n!⋅4ⁿ)
Also It'sΩ(n!⋅4ⁿ)
.Just important thing is what you doing in your steps? If each step is O(1) this notations hold, but in other cases, it's depend to your steps, I suggest show us your function, to see what's the steps.
And why you can't say it's
O(n!)
? because you can't find constantc
such that:because for any constant
c
when4ⁿ > c
(for example whenn ≥ c
) above inequality is wrong.如果它完全执行
n!*4^n
步,那么就没有必要使用大的oh符号。是的,这意味着它的复杂度为 O(n!*4^n)。
If it does exactly
n!*4^n
steps, there's no real need for big oh notation.And yes, that means it has
O(n!*4^n)
complexity.