java - 如何判断给定函数是否是 O(n)？

Question

我在测试中遇到了以下问题:

以下哪些是 O(n) 的？

a) n + lgn
b) n + 2n
c) n + n^2
d) 1000n + 4500lgn + 54n

我知道 O(n) 的时间复杂度取决于元素的数量，因此随着元素数量的增加，完成操作所需的时间也会增加。按照这个逻辑，a和c的时间复杂度是O(n)对吗？

Answer 1

考虑 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^2 O(n^2)？您应该不会在查找值 c > 0 时遇到麻烦。和k > 0 , n >= k ，这样 0 <= n + n^2 <= cn^2 .

看看 https://xlinux.nist.gov/dads//HTML/bigOnotation.html供进一步阅读。