s********k
发帖数: 6180 | 1 【 以下文字转载自 CS 讨论区 】
发信人: silverhawk (silverhawk), 信区: CS
标 题: Big O的表示问题
发信站: BBS 未名空间站 (Mon Oct 4 17:46:28 2010, 美东)
想请问 比如 N^3-N^2+N 可以写成 O(N^3)吗, 还是应该写成其他更精确的形式？ |
X****r
发帖数: 3557 | 2 可以。理论上你写成O(N^4)都可以，不过没人这么用。
【在 s********k 的大作中提到】
: 【 以下文字转载自 CS 讨论区 】
: 发信人: silverhawk (silverhawk), 信区: CS
: 标 题: Big O的表示问题
: 发信站: BBS 未名空间站 (Mon Oct 4 17:46:28 2010, 美东)
: 想请问 比如 N^3-N^2+N 可以写成 O(N^3)吗, 还是应该写成其他更精确的形式？
|
s********k
发帖数: 6180 | 3 了解，那么O(N^3)是最精确的表示了吗？没有O(N^3)-O(N^2)+O(N)这样的表示吧
【在 X****r 的大作中提到】
: 可以。理论上你写成O(N^4)都可以，不过没人这么用。
|
X****r
发帖数: 3557 | 4 O()的结果是一个集合，不能这样加减。
准确地说应该这样写（这里用LaTex的记号表示方法）：N^3-N^2+n \in O(N^3)
O(N^3)和O(N^3-N^2+N)是同一个集合，所以没有人用后者。
O只是上界，要精确表示的话还有下界。比如\Theta记号表示上下界：
N^3-N^2+N \in \Theta(N^3)
【在 s********k 的大作中提到】
: 了解，那么O(N^3)是最精确的表示了吗？没有O(N^3)-O(N^2)+O(N)这样的表示吧
|
s********k
发帖数: 6180 | 5 谢谢，请问下\Theta 表示上届吗？和big O有什么区别？
【在 X****r 的大作中提到】
: O()的结果是一个集合，不能这样加减。
: 准确地说应该这样写（这里用LaTex的记号表示方法）：N^3-N^2+n \in O(N^3)
: O(N^3)和O(N^3-N^2+N)是同一个集合，所以没有人用后者。
: O只是上界，要精确表示的话还有下界。比如\Theta记号表示上下界：
: N^3-N^2+N \in \Theta(N^3)
|
n******n
发帖数: 12088 | 6 ft. 那不就是O(N^3)吗？
【在 s********k 的大作中提到】
: 谢谢，请问下\Theta 表示上届吗？和big O有什么区别？
|
X****r
发帖数: 3557 | 7 http://en.wikipedia.org/wiki/Big_O_notation
【在 s********k 的大作中提到】
: 谢谢，请问下\Theta 表示上届吗？和big O有什么区别？
|
s*****g
发帖数: 5159 | 8 By definition of Big O
O(f(n)): For any positive real constant C, there is a positive integer N (a
function of C), such that for all n > N, the complexity of the algorithm is
strictly less than f(n).
【在 s********k 的大作中提到】
: 【 以下文字转载自 CS 讨论区 】
: 发信人: silverhawk (silverhawk), 信区: CS
: 标 题: Big O的表示问题
: 发信站: BBS 未名空间站 (Mon Oct 4 17:46:28 2010, 美东)
: 想请问 比如 N^3-N^2+N 可以写成 O(N^3)吗, 还是应该写成其他更精确的形式？
|
c*******t
发帖数: 1095 | 9 上下界都表示了
O表上界
\Omiga表下界
\Omiga(f(n))<\Theat(f(n))
【在 s********k 的大作中提到】
: 谢谢，请问下\Theta 表示上届吗？和big O有什么区别？
|
