如何找出给定函数是否为 O(n)？
How to find out whether a given function is O(n)?
我在测试中遇到了以下问题：
O(n) 中有以下哪些项？
a) n + lgn
b) n + 2n
c) n + n^2
d) 1000n + 4500lgn + 54n
我知道 O(n) 的时间复杂度取决于元素的数量，因此随着元素数量的增加，完成操作所需的时间也会增加。按照这个逻辑，a和c的时间复杂度是O(n)对吗？
考虑 O(n) 的定义，即对于某些函数 f(n) 必须有两个正常数，c 和 k，使得 c > 0 、k > 0、n >= k 和 0 <= f(n) <= cn。如果我们可以证明常量 c 和 k 存在那么函数就是 O(n)（如果这些常量不存在那么函数实际上大于 O(n)）。
让我们看看F(n) = n + lg(n)。这是O(n)吗？如果是这样，那么我们应该可以轻松找到 c 和 k 的值。
0 <= f(n) <= cn
0 <= n + lg(n) <= cn
让我们将 k 设置为 2 并考虑 n 为 2 的基本情况（因为 n >= k）。
0 <= 2 + lg(2) <= c * 2
0 <= 2 + 1 <= 2c
0 <= 3 <= 2c
0 <= 3/2 <= c
让我们看看函数在 n 增加时的行为（让我们设置 n = 4 看看会发生什么）。
0 <= 4 + lg(4) <= c * 4
0 <= 4 + 2 <= 4c
0 <= 6 <= 4c
0 <= 6/4 <= c
0 <= 3/2 <= c .. take a look at that, it doesn't matter how large n becomes, c is 3/2
所以我们找到了常量（c=3/2 和 k=2），因此根据正式定义，这个函数是 O(n)。
让我们看看F(n) = n + n^2。这是O(n)吗？很明显它不是，它实际上是 O(n^2)，但让我们看看我们是否能找到值 c 和 k。
0 <= f(n) <= cn
0 <= n + n^2 <= cn
让我们再次将 k 设置为 2 并考虑 n = k 的基本情况。
0 <= 2 + 2^2 <= c*2
0 <= 2 + 4 <= 2c
0 <= 6 <= 2c
0 <= 3 <= c .. so IF this is O(n), c is at least 3
让我们看看当 n 增加时会发生什么（现在 n = 4）
0 <= 4 + 4^2 <= 4c
0 <= 4 + 16 <= 4c
0 <= 20 <= 4c
0 <= 20/4 <= c
0 <= 5 <= c .. last time c was 3, now its 5 ... as n increases, c is not constant!
这个函数不是 O(n) - 我们找不到常数值 c 和 k 因为它们根本不存在。
考虑 f(n) = 5n ...这是 O(n)（在这种情况下，很明显 c 是 5）。考虑 f(n) = n * n .. 这不是 O(n)（c 将等于 n，它不是常量）。我们真正要说的是我们的函数 f(n) 受另一个函数 g(n) 乘以某个常数的限制。当我们询问函数是否为 O(n) 时，我们让 g(n) = n，但是 n^2、lgn、nlgn 都是有趣的边界（可能会在测试中） .
是n + n^2O(n^2)吗？查找值 c > 0 和 k > 0、n >= k 应该不会有问题，这样 0 <= n + n^2 <= cn^2.
看看
https://xlinux.nist.gov/dads//HTML/bigOnotation.html 进一步阅读。
我在测试中遇到了以下问题：
O(n) 中有以下哪些项？
a) n + lgn
b) n + 2n
c) n + n^2
d) 1000n + 4500lgn + 54n
我知道 O(n) 的时间复杂度取决于元素的数量，因此随着元素数量的增加，完成操作所需的时间也会增加。按照这个逻辑，a和c的时间复杂度是O(n)对吗？
考虑 O(n) 的定义，即对于某些函数 f(n) 必须有两个正常数，c 和 k，使得 c > 0 、k > 0、n >= k 和 0 <= f(n) <= cn。如果我们可以证明常量 c 和 k 存在那么函数就是 O(n)（如果这些常量不存在那么函数实际上大于 O(n)）。
让我们看看F(n) = n + lg(n)。这是O(n)吗？如果是这样，那么我们应该可以轻松找到 c 和 k 的值。
0 <= f(n) <= cn
0 <= n + lg(n) <= cn
让我们将 k 设置为 2 并考虑 n 为 2 的基本情况（因为 n >= k）。
0 <= 2 + lg(2) <= c * 2
0 <= 2 + 1 <= 2c
0 <= 3 <= 2c
0 <= 3/2 <= c
让我们看看函数在 n 增加时的行为（让我们设置 n = 4 看看会发生什么）。
0 <= 4 + lg(4) <= c * 4
0 <= 4 + 2 <= 4c
0 <= 6 <= 4c
0 <= 6/4 <= c
0 <= 3/2 <= c .. take a look at that, it doesn't matter how large n becomes, c is 3/2
所以我们找到了常量（c=3/2 和 k=2），因此根据正式定义，这个函数是 O(n)。
让我们看看F(n) = n + n^2。这是O(n)吗？很明显它不是，它实际上是 O(n^2)，但让我们看看我们是否能找到值 c 和 k。
0 <= f(n) <= cn
0 <= n + n^2 <= cn
让我们再次将 k 设置为 2 并考虑 n = k 的基本情况。
0 <= 2 + 2^2 <= c*2
0 <= 2 + 4 <= 2c
0 <= 6 <= 2c
0 <= 3 <= c .. so IF this is O(n), c is at least 3
让我们看看当 n 增加时会发生什么（现在 n = 4）
0 <= 4 + 4^2 <= 4c
0 <= 4 + 16 <= 4c
0 <= 20 <= 4c
0 <= 20/4 <= c
0 <= 5 <= c .. last time c was 3, now its 5 ... as n increases, c is not constant!
这个函数不是 O(n) - 我们找不到常数值 c 和 k 因为它们根本不存在。
考虑 f(n) = 5n ...这是 O(n)（在这种情况下，很明显 c 是 5）。考虑 f(n) = n * n .. 这不是 O(n)（c 将等于 n，它不是常量）。我们真正要说的是我们的函数 f(n) 受另一个函数 g(n) 乘以某个常数的限制。当我们询问函数是否为 O(n) 时，我们让 g(n) = n，但是 n^2、lgn、nlgn 都是有趣的边界（可能会在测试中） .
是n + n^2O(n^2)吗？查找值 c > 0 和 k > 0、n >= k 应该不会有问题，这样 0 <= n + n^2 <= cn^2.
看看 https://xlinux.nist.gov/dads//HTML/bigOnotation.html 进一步阅读。