我看了很多关于渐近符号的讲座、视频和资源。我明白 O、Omega 和 Theta 是什么。但是在算法中，为什么我们总是只使用 Big Oh 符号，为什么不使用 Theta 和 Omega(我知道这听起来很笨，但请帮助我)。按照算法，这个上限和下限到底是什么？
我的下一个问题是，我们如何从算法中找到复杂性。假设我有一个算法，我如何找到递归关系 T(N) 然后计算它的复杂性？我如何形成这些方程式？就像使用递归方式的线性搜索一样，T(n)=T(N-1) + 1。如何？
如果有人可以解释我是一个新手，这样我就能更好地理解，那就太好了。我在 StackOverFlow 中找到了一些答案，但不够令人信服。
谢谢。
最佳答案
与 Theta 和 Omega 相比，为什么我们如此频繁地使用 big-O:这在一定程度上是文化原因，而不是技术原因。当 Theta 真的更合适时，人们说大 O 是非常普遍的。 Omega 在实践中使用不多，因为我们通常更关心上界而不是下界，也因为非平凡的下界通常更难证明。 (琐碎的下界通常是那种说“你必须查看所有输入，所以运行时间至少等于输入的大小。”)
当然，这些关于下界的评论也部分解释了 Theta，因为 Theta 既涉及上界也涉及下界。
提出递归关系:没有解决所有情况的简单方法。这是相对简单的递归算法的描述。
令 N 为初始输入的大小。假设你的递归函数中有 R 次递归调用。 (示例:对于合并排序，R 将为 2。)进一步假设所有递归调用将初始输入的大小减少相同的数量，从 N 到 M。(示例:对于合并排序，M 将为 N/2。)最后，假设递归函数 在递归调用之外工作。(示例:对于合并排序，对于合并，W 将是 N。)
那么递归关系就是 T(N) = R*T(M) + W。(例如:对于合并排序，这将是 T(N) = 2*T(N/2) + N。)
关于algorithm - 渐近符号和通过分析算法形成递推关系，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11915603/