Big-O 的非正式概念被描述为“它是函数的最高增长阶”，即 f(n) = 3n^2 + 5n + 50 就是 O(n^2)。
我确实理解 Big-O 只是一种说“保证不会比这个时期更糟”的方式。形式上，定义似乎是 f(n) -> O(g(n)) iff f(n) <= c * g(n) 其中 c 是正数
首先是一些数学的东西..如果 f(n) = 5n^2, g(n)=n 我应该能够通过这样做来证明 5n^2 不是 O(g(n))
5n^2 <= cn
5n <= c
如果这个想法是 c 不是一个常数（我不知道这是否是一个要求），那就是证明 f(n) 不在 O(g(n)) 中，如果 g(n) 是n^3（肯定应该包含其中）？
5n^2 <= cn^3
5/n <= c
我对我假设的所有这些数学是如何计算的有一个误解，所以我问：
所有这些花哨的东西是如何工作的
它如何连接到我的数据结构类中给出的简单定义？
谢谢你的帮助
c是一个常数（即独立于n）
在你的第一个例子中（这是矛盾的证明）：即假设
5n^2 <= cn
5n <= c
但是对于任何固定常数 c，我们可以找到一个使其不真实的 n 值。
例如选择 c = 1000000，那么 n = 200001 的值将是矛盾的。
在您的第二个示例中，我们知道 f(n) 是 O(n^2)，因此它也是 O(n^3) 及以上。如果你以 k(n^2) 为界，那么你也以 j(n^3) 为界
n是一个正整数，这意味着 ，1<=n因此5/n<=5/1=5，所以你可以选择c=5。
更完整的定义还允许您选择n0and a，这两个常量，并且只证明f(n)<=a+c*g(n)对于所有n0<n
Big-O 的非正式概念被描述为“它是函数的最高增长阶”，即 f(n) = 3n^2 + 5n + 50 就是 O(n^2)。
我不会说这是 Big-O 背后的想法。非正式地，Big-O 是对给定函数不能超过的粗略估计。它的使用主要是近似于大数字的增长方式。
例如，如果我们取一个 6 位数的数字，我们可以肯定地说它小于百万，而无需查找它的位数。很多情况下这已经足够了，我们不需要分析所有数字。
对于分析功能增长，有两个因素发挥作用：
f大于g，但我们可以通过乘以g一些大常数来修复它，这意味着f的优势不是因为增长这将我们引向定义的两个部分：（1）一些常数和（2）对于足够大的 n
实际上，对于多项式，高阶分量定义了增长速度。