f(n)= 1000n + 4500lgn + 54n O(n)？

Question

我的测试中给出了以下问题:

f(n)= 1000n + 4500lgn + 54n O(n)？

我通过应用以下定义回答了这个问题:

O(n)的定义,对于某些函数f(n),必须有两个正常数c和k,使得c> 0,k> 0,n> = k,并且0 <= f(n )<= cn.如果我们可以证明常数c和k存在,那么函数是O(n)(如果那些常数不存在那么函数实际上大于O(n)).

解:

0≤+ 1000N + 4500lgn 54N≤CN
0≤4000 + 9000 + 216≤4c中当k = 4
0≤3304≤Ç

当n = 8>
k0≤21932≤8n0≤2741.5≤n时,0≤8000 + 13500 +
432≤8n(上次c = 3304,但现在为2741.5 ......当n增加时,c不是常数!)

结论:
这个函数不是O(n) - 我们找不到常数值c和k,因为它们根本就不存在.

我的解决方案是否正确

Answer 1

0≤2741.5≤n(上次c = 3304,但现在是2741.5 ....当n增加时,c不是常数!)

解决方案中的缺陷是,如果您坚持使用原始值c,则仍然会满足约束条件.重要的不是常数的实际值,只是存在一对常数,c并且所有人k都不满足不等式.n > k

在这个问题的答案中,我不知道(由你的老师)需要多严格的严格程度.然而,严格的解决方案需要一个数学证明(从第一原则或建立定理),要么c和k不存在¹,或者他们可以不存在.

^{1 -一对c和k你能证明确实满足了约束所有的N > k将是一个充分证明.}