我看过很多关于渐近符号的讲座,视频和资料。我知道O,ω和θ是什么。但是在算法中,为什么我们总是只使用大的Oh符号,为什么不使用θ和ω(我知道这听起来不太好,但是请帮助我)根据算法,这个上界和下界到底是什么?
我的下一个问题是,我们如何从算法中找到复杂性。假设我有一个算法,我如何找到递归关系T(n),然后计算它的复杂性?我如何形成这些方程?类似于使用递归方式进行线性搜索的情况,t(n)=t(n-1)+1。怎么用?
如果有人能解释我认为我是个傻瓜,这样我就能更好地理解我,那就太好了我找到了一些答案,但在stackoverflow中没有足够的说服力。
谢谢您。

最佳答案

当我们创建一个算法,它总是为了最快,我们需要考虑每一个情况这就是为什么我们使用O的原因,因为我们希望使复杂性更大,并且确保我们的算法永远不会超过这个。
为了评估复杂性,你必须计算步长。在t(n)=t(n-1)+1的方程中,计算t(0)之前有n步,则一致性是线性的。(我说的是时间复杂度而不是空间复杂性)。

关于algorithm - 通过分析算法渐近符号和形成递推关系,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/11915603/

10-09 20:10
查看更多