Sou*_*abh 2 big-o asymptotic-complexity
遇到此陈述时，我正在阅读Thomas H. Corman的算法介绍（渐进表示法）
当a> 0时，任何线性函数an + b都在O（n ^ 2）中，这实际上可以通过取c = a + | b |来验证。并且没有= max（1，-b / a）
我不明白为什么O（n ^ 2）而不是O（n）。O（n）上限何时会失败。
例如，3n+2根据该书
3n+2 <= (5)n^2 n>=1
但这也很好
3n+2 <= 5n n>=1
那么，为什么上限是n ^ 2呢？
好吧，我找到了本书的相关部分。确实，摘录来自介绍big-O符号和亲属的章节。
big-O的正式定义是，所讨论的函数没有比比较函数渐近地增长。它没有说函数是否渐近增长，所以：
f(n) = n在中O(n)，O(n^2)也O(e^n)因为n它的渐近性没有比任何一个都快。但是n不在O(1)。
和中的任何功能O(n)也都在O(n^2)和中O(e^n)。
如果要描述紧的渐近界线，可以使用big-Θ表示法，它在本书的big-O表示法之前介绍。f(n) ∊ Θ(g(n))意味着它的f(n)渐近增长不会比反之快g(n)。因此f(n) ∊ Θ(g(n))等于f(n) ∊ O(g(n))和g(n) ∊ O(f(n))。
所以f(n) = n在Θ(n)但不是在Θ(n^2)或Θ(e^n)或Θ(1)。
另一个示例：f(n) = n^2 + 2在中，O(n^3)但不在Θ(n^3)中Θ(n^2)。
您需要将其O(...)视为一个集合（这就是为什么使用集合理论的“ element-of”符号）的原因。O(g(n))是不渐近增长的所有函数的集g(n)，而Θ(g(n))既不渐近增长也不慢的函数集g(n)。因此，逻辑上的后果是这Θ(g(n))是的子集O(g(n))。
通常=用它代替∊符号，这确实会引起误解。它是纯符号，不与实际共享任何属性=。例如1 = O(1)和2 = O(1)，但不会1 = O(1) = 2。最好避免使用=big-O表示法。但是，稍后您会看到该=符号很有用，例如，如果您想表达其余术语的复杂性，例如：f(n) = 2*n^3 + 1/2*n - sqrt(n) + 3 = 2*n^3 + O(n)，这意味着渐近函数的行为类似2*n^3，而被忽略的部分的渐近增长不会比快n。
所有这些都与big-O表示法的典型用法背道而驰。您通常会发现由它定义的算法的时间/内存复杂性，实际上它应该由big-Θ表示法定义。例如，如果您的算法中O(n^2)有in O(n)，in中有in ，那么第一个算法实际上可能仍会渐近加快，因为它也可能在in中Θ(1)。造成这种情况的原因有时可能是紧密的Θ界限不存在或对于给定算法未知，因此至少big-O可以确保事情花费的时间不会超过给定界限。按照惯例，您始终尝试给出已知的最低big-O界限，而这在形式上不是必需的。