因此，下学期我将开设一门算法课程，我正在为此做准备。我从渐近分析开始。只要我能找到一个常数C和某个数字n> no，其中f（x）<= C * g（x），那本书似乎就说明了，那么我可以得出f（x）= O（g（x） ）。似乎需要归纳推理来证明它对所有n都成立，而这本书并没有说明！我还看到有些人使用大O的定义来回答问题（尽管这样做很少），但我在书中没有看到。即O是：
f（x）= O（g（x））如果lim n->∞f（x）/ g（x）存在
这被认为是确定渐近边界的更严格的证明吗？
如果是这种情况，我认为Ω是：
f（x）=Ω（g（n））如果lim n->∞f（x）/ g（x）> 0
和Θ为：f（x）=Ω（g（n））Λf（x）=Ω（g（n））
[没有老师问，我不确定解决这类问题的最佳方法是什么。
一个例子是确定之间的关系f（n）= nlog n和g（n）= n *√n
您在这里问了几个问题。让我们依次解决每个问题：
这本书似乎陈述了，只要我能找到一个常数C和一些数字n>不，其中f（x）<= C * g（x），那么我可以得出f（x）= O（g（ X））。似乎需要归纳推理来证明它对所有n都成立，而这本书并没有说明！
这确实是big-O表示法的正式定义。但是，关于此定义的任何内容都不需要使用归纳法。例如，假设我要证明2n + 137 = O（n）。我将选择c = 3和n 0并显示这些常量具有我们想要的属性。具体来说，选择任何n≥137。然后
2n + 137
≤2n + n（因为137≤n）
= 3n，
并且我们不用任何归纳便到达了这里。
[我还看到有些人使用大O的定义来回答问题（尽管这样做很少），但我在书中没有看到。即O是：
f（x）= O（g（x）），如果lim n->∞f（x）/ g（x）存在]
这被认为是确定渐近边界的更严格的证明吗？
这很有趣。想象f和g是存在lim n→∞（f（n）/ g（n））的函数。那么实际上您将拥有f（n）= O（g（n））。一种看待这种情况的方法是使用无穷大极限的形式定义。具体来说，如果L是有限的，那么根据定义
lim n→∞ h（n）= L当且仅当对于任何ε> 0，存在n ε使得| h（n）-L |对于所有n≥n ε的≤ε。
因此，假设lim n→∞ = L对于某个常数L。现在，选择ε= 1，所以有n 1，对于任何n≥n 1，我们都有] >
| f（n）/ g（n）-L | ≤1。
特别是那意味着
f（n）/ g（n）-L≤1，
所以
= n 1然后给我们常数，我们需要证明f（n）= O（g（n））。f（n）≤（1 + L）g（n）
选择c = 1 + L且n 0
以不同的方式陈述，如果存在该限制，则f（n）= O（g（n））。
但是，即使该限制不存在，也可能f（n）= O（g（n））。例如，选择f（n）= 2 + sin n和g（n）=1。然后f（n）= O（g（n）），但是f（n）/ g（n）的极限不存在t是因为这些值朝着无穷大方向振荡。因此，事实并非如此。
[我认为-但不是100％肯定-如果您用更高的限制代替限制，那么您将获得等价，但这是我需要更多考虑的事情。
这是做大O证明的更“严格”的方法吗？我不会这么说。它和其他方法一样严格，尽管如果您要建立直觉，这可能会更有益。
如果是这种情况，我认为Ω是：
f（x）=Ω（g（n）），如果lim n->∞f（x）/ g（x）> 0
并且Θ是：f（x）=Ω（g（n））Λf（x）=Ω（g（n））
非常接近！如上所述，极限技巧不是big-O表示法的“定义”，因为它不能处理所有情况，因此您不能以这种方式定义Ω表示法。但是，您对Θ符号的定义是随意的。
希望这会有所帮助，祝你好运！