p**f
发帖数: 3549 | 1 我知道大O和Θ的区别，Θ是上下夹趋近，大O只是上趋近。Θ(n)好理解。
可是为什么线性函数an+b的复杂度是O(n^2)，而不是O(n)？
就算是根据定义：
O(g(n)) = {f(n): 存在一个正数c, n0使得 0<=f(n)<=cg(n), for n>=n0}
对于任意an+b(假设a, b都是正数), 我取c=(a+1), n0=(b+1)，就可以满足上述不等式
吧，
即：0 <= an+b <= (a+1)n, for n>=(b+1).
所以还是O(n)啊。
百思不得其姐。求指点。 | N******K
发帖数: 10202 | 2 a*n+b
一个乘法 一个加法 哪里来的o(n) ?
【在 p**f 的大作中提到】
: 我知道大O和Θ的区别，Θ是上下夹趋近，大O只是上趋近。Θ(n)好理解。
: 可是为什么线性函数an+b的复杂度是O(n^2)，而不是O(n)？
: 就算是根据定义：
: O(g(n)) = {f(n): 存在一个正数c, n0使得 0<=f(n)<=cg(n), for n>=n0}
: 对于任意an+b(假设a, b都是正数), 我取c=(a+1), n0=(b+1)，就可以满足上述不等式
: 吧，
: 即：0 <= an+b <= (a+1)n, for n>=(b+1).
: 所以还是O(n)啊。
: 百思不得其姐。求指点。
| f*******n
发帖数: 12623 | 3 你不是说了吗？O只是上趋近。所以所有O(n)的，也同时是O(n^2)，也同时是O(2^n)，
或甚至说是O(2^2^2^2^n)都没错。
所以O不一定代表什么。最准确的是Θ(n)，就是O(n)而且Ω(n)。O只是上趋近、Ω只是
下趋近、Θ是上下夹趋近。
【在 p**f 的大作中提到】
: 我知道大O和Θ的区别，Θ是上下夹趋近，大O只是上趋近。Θ(n)好理解。
: 可是为什么线性函数an+b的复杂度是O(n^2)，而不是O(n)？
: 就算是根据定义：
: O(g(n)) = {f(n): 存在一个正数c, n0使得 0<=f(n)<=cg(n), for n>=n0}
: 对于任意an+b(假设a, b都是正数), 我取c=(a+1), n0=(b+1)，就可以满足上述不等式
: 吧，
: 即：0 <= an+b <= (a+1)n, for n>=(b+1).
: 所以还是O(n)啊。
: 百思不得其姐。求指点。
|
|
