我正在学习大O符号,但是我对这道题的解法有困惑:
Is 2n + 10 ≡ O(n)?
Can we find c and n0?
2n + 10 <= cn
(c-2)n >= 10
n >= 10/(c-2)
Pick c = 3 and n0 = 10
这个例子中还使用了一个图形:
我不知道为什么c = 3,n0 = 10。请有人给我解释一下吗?
我正在学习大O符号,但是我对这道题的解法有困惑:
Is 2n + 10 ≡ O(n)?
Can we find c and n0?
2n + 10 <= cn
(c-2)n >= 10
n >= 10/(c-2)
Pick c = 3 and n0 = 10
这个例子中还使用了一个图形:
我不知道为什么c = 3,n0 = 10。请有人给我解释一下吗?
我会以不同的方式解决 2n + 10 <= cn
。
2n + 10 <= cn
2 + 10/n <= c //divide by n
c >= 2 + 10/n
显然,c
必须大于2。现在选择一个你喜欢的大于2的数字。嗯,c=2.718
。这样就得到了:
2n + 10 <= 2.718*n
10 <= 0.718*n //subtract 2n
13.93 <= n
2n + 10 <= c*n
。如果我们取c=2.718
和n
大于15
。(15是因为它比极限值13.93大,而且我喜欢15。)c=3
可能更容易。这将给出2n + 10 <= 3*n
10 <= n //subtract 2n
说一个函数 f(n)
是 O(n)
意味着你可以找到 c
和 n0
,使得对于所有的 n >= n0
,f(n) <= cn
。
要在您的情况下验证这一点:如果 n >= 10
,那么:
f(n) = 2n + 10
<= 3n // because 10 <= n
= cn
对于所有n >= 10,有f(n) <= cn
,因此f(n)
是一个O(n)
函数。
请注意,其他c
和n0
的值也可以使用;您只需要找到一对即可。
let f(n) = 2n+10
as per the Big-Oh notation,
f(n)<= c*g(n) ----->eq1(let)
2n+10 <= 2n+n
2n+10 <= 3n for n>=10 //here the constant 10 is replaced by n ---->eq2
比较方程式eq1和eq2 c=3以及g(n)=n,当n=10时的值
f(n)= O(g(n)) = O(n)
10*N^3+ 23*N^2 + 43*N + 154 = O(N^3)