算法中的大O
big O in algorithm
我看过算法导论里面关于大O的定义哪本书没有讲到我的困惑。
根据它的定义，大家都知道函数T(n) = 3n属于O(n)，我的困惑是属于O(n)的函数是否都属于O(n ^2) and O(n^3) and O(n^4) and O(n^k) k>1, 因为大O描述的是上限，我差点就能找到正整数常数c和正整数常数n0满足0<=3n<=cn^2当n>=n0，如果答案是肯定的，为什么人们更喜欢用O(n)来描述T(n)=3n如果它定义很严重？
更多，这些符号（big O, big theta, big omega）在其他数学领域的哪些地方使用过？
请 post 必要的参考资料或任何其他讨论此内容的书籍
部分答案：您的理解是正确的，O(n) 是 O(n^k) 的严格子集，其中 k > 1。
为什么我们更喜欢 O(n)：如果你问一些产品的价格（实际成本 25），你更喜欢哪个答案：a）最多 100 或 b）最多 30。
说 f(n) 在 O(n) 中比说它在 O(n^2) 中提供更多关于 f(n) 的信息。
它还有什么用？例如描述近似值的误差项。
f(n)=O(g(n))确实表示g(n)是渐近意义上f(n)的上界，任何函数h(n)≥g(n)也是上界，f(n)=O(h(n)).
例如f(n)=O(n) => f(n)=O(n²).
但很明显，对目标函数进行更接近建模的上界更有趣，据说紧。因此，在可能的上界中，选择已知的最紧界。
对于某些函数，可能会出现相同的 g(n) 也是下界（具有不同的渐近常数），我们表示为 f(n)=Ω(g(n))。在这种情况下，边界是双向的，并且写成 f(n)=Θ(g(n)).
当然还有 3n=Θ(n)，但是 3n<>Θ(n²)。
我看过算法导论里面关于大O的定义哪本书没有讲到我的困惑。
根据它的定义，大家都知道函数T(n) = 3n属于O(n)，我的困惑是属于O(n)的函数是否都属于O(n ^2) and O(n^3) and O(n^4) and O(n^k) k>1, 因为大O描述的是上限，我差点就能找到正整数常数c和正整数常数n0满足0<=3n<=cn^2当n>=n0，如果答案是肯定的，为什么人们更喜欢用O(n)来描述T(n)=3n如果它定义很严重？
更多，这些符号（big O, big theta, big omega）在其他数学领域的哪些地方使用过？
请 post 必要的参考资料或任何其他讨论此内容的书籍
部分答案：您的理解是正确的，O(n) 是 O(n^k) 的严格子集，其中 k > 1。
为什么我们更喜欢 O(n)：如果你问一些产品的价格（实际成本 25），你更喜欢哪个答案：a）最多 100 或 b）最多 30。 说 f(n) 在 O(n) 中比说它在 O(n^2) 中提供更多关于 f(n) 的信息。
它还有什么用？例如描述近似值的误差项。
f(n)=O(g(n))确实表示g(n)是渐近意义上f(n)的上界，任何函数h(n)≥g(n)也是上界，f(n)=O(h(n)).
例如f(n)=O(n) => f(n)=O(n²).
但很明显，对目标函数进行更接近建模的上界更有趣，据说紧。因此，在可能的上界中，选择已知的最紧界。
对于某些函数，可能会出现相同的 g(n) 也是下界（具有不同的渐近常数），我们表示为 f(n)=Ω(g(n))。在这种情况下，边界是双向的，并且写成 f(n)=Θ(g(n)).
当然还有 3n=Θ(n)，但是 3n<>Θ(n²)。