s********k
发帖数: 6180 | 1 假如我想表示一个函数F对N的变化， 这个函数可以明确的表示为F=alpha×N， 那么我
再用F=alpha×O(N)表示还合适否？ |
l******e
发帖数: 470 | 2 没错
合适不合适不知道。。
【在 s********k 的大作中提到】
: 假如我想表示一个函数F对N的变化， 这个函数可以明确的表示为F=alpha×N， 那么我
: 再用F=alpha×O(N)表示还合适否？
|
s********k
发帖数: 6180 | 3 或者说用big O表达更准确吗？
【在 l******e 的大作中提到】
: 没错
: 合适不合适不知道。。
|
a****9
发帖数: 418 | 4 只要a是常数, a*O(n)就没有意义
因为f=O(n)的意思就是存在一个常数, 比如C使得f<=C*N
C可以随便取
【在 s********k 的大作中提到】
: 或者说用big O表达更准确吗？
|
s********k
发帖数: 6180 | 5 但是我现在知道的常数的情况下，那么直接表达比用O（N）表达更准确了？
【在 a****9 的大作中提到】
: 只要a是常数, a*O(n)就没有意义
: 因为f=O(n)的意思就是存在一个常数, 比如C使得f<=C*N
: C可以随便取
|
a****9
发帖数: 418 | 6 你是说 比如 1.326*N vs O(N) ?
前者精确
【在 s********k 的大作中提到】
: 但是我现在知道的常数的情况下，那么直接表达比用O（N）表达更准确了？
|
s********k
发帖数: 6180 | 7 我看到很多地方用这样的表示：k1+k2*O(NlogN),这样的表示和k1+k2*NlogN有什么区别
吗？还是说后者更精确？而用big O表示的是上限？quick sort里面的O(NlogN)是否也
能表示成为NlogN?另外像你例子里面的1.326N，能表示成为O(1.326N)吗？谢谢
【在 a****9 的大作中提到】
: 你是说 比如 1.326*N vs O(N) ?
: 前者精确
|
s********k
发帖数: 6180 | 8 或者说1.2N和0.01N都是O(N),用O(N)表示不出他们的差别？还是可表示成1.2*(N)以及0
.01*O(N)
【在 s********k 的大作中提到】
: 我看到很多地方用这样的表示：k1+k2*O(NlogN),这样的表示和k1+k2*NlogN有什么区别
: 吗？还是说后者更精确？而用big O表示的是上限？quick sort里面的O(NlogN)是否也
: 能表示成为NlogN?另外像你例子里面的1.326N，能表示成为O(1.326N)吗？谢谢
|
x***u
发帖数: 336 | 9 O(N)是一个family of functions，表示所有增长速度是线性或以下的函数。1.2N, 0.
1N, 1000000000000000000000000N, \sqrt{n}都是这个family里的。
及0
【在 s********k 的大作中提到】
: 或者说1.2N和0.01N都是O(N),用O(N)表示不出他们的差别？还是可表示成1.2*(N)以及0
: .01*O(N)
|
a****9
发帖数: 418 | 10 1.2*O(N)也好 0.01*O(N)也好
你这个常量怎么得来呢?
因为O(N)本身也不是一个定值阿
你是不是improve了一个算法
虽然没有降阶 但是速度提高了,
想表达出来?
及0
【在 s********k 的大作中提到】
: 或者说1.2N和0.01N都是O(N),用O(N)表示不出他们的差别？还是可表示成1.2*(N)以及0
: .01*O(N)
|
|
|
s********k
发帖数: 6180 | 11 对。类似的想法，当然我这里不是算法的时间复杂度，主要是表示某个网络协议的空间
复杂度。这样用O（N）表示合适吗？还是直接用比如1.2N之类的？不过我看也有表示1.
2*O(N)的，不知道哪种更合适？
【在 a****9 的大作中提到】
: 1.2*O(N)也好 0.01*O(N)也好
: 你这个常量怎么得来呢?
: 因为O(N)本身也不是一个定值阿
: 你是不是improve了一个算法
: 虽然没有降阶 但是速度提高了,
: 想表达出来?
:
: 及0
|
w**********s
发帖数: 291 | 12 这里k1 和k2应该是和N独立的变量，所以可以这样表达。如果只是常数，那么k1 + k2*
O(NlogN)是没有
意义的。
O(1.326N) 没有意义，它= O(N)
如果你得出了1.326N，那肯定比O(N)要好很多。
看看wiki就明白了吧。
【在 s********k 的大作中提到】
: 我看到很多地方用这样的表示：k1+k2*O(NlogN),这样的表示和k1+k2*NlogN有什么区别
: 吗？还是说后者更精确？而用big O表示的是上限？quick sort里面的O(NlogN)是否也
: 能表示成为NlogN?另外像你例子里面的1.326N，能表示成为O(1.326N)吗？谢谢
|
s********k
发帖数: 6180 | 13 improve了一个算法,虽然没有降阶,空间复杂度减少了，怎么表达？
k2*
【在 w**********s 的大作中提到】
: 这里k1 和k2应该是和N独立的变量，所以可以这样表达。如果只是常数，那么k1 + k2*
: O(NlogN)是没有
: 意义的。
: O(1.326N) 没有意义，它= O(N)
: 如果你得出了1.326N，那肯定比O(N)要好很多。
: 看看wiki就明白了吧。
|
w**********s
发帖数: 291 | 14 空间复杂度也是算法的性能指标之一，只是不像时间复杂度一样重要，除非你的问题中
，存储是一个
极大的瓶颈。
要么你这个improvement比较significant，而且问题的存储背景够强，否则可能没人会
太关心你的结果。
【在 s********k 的大作中提到】
: improve了一个算法,虽然没有降阶,空间复杂度减少了，怎么表达？
:
: k2*
|
s********k
发帖数: 6180 | 15 结果对于我来说还是比较重要吧，比如从10*N 改进到0.1*N,这种情况下用O(N)表示就
显现不出差距了，但是事实上差距还是比较大。这种情况不用big O而是直接表示比较
合适？
【在 w**********s 的大作中提到】
: 空间复杂度也是算法的性能指标之一，只是不像时间复杂度一样重要，除非你的问题中
: ，存储是一个
: 极大的瓶颈。
: 要么你这个improvement比较significant，而且问题的存储背景够强，否则可能没人会
: 太关心你的结果。
|
S*******w
发帖数: 24236 | 16
～～～是的。
【在 s********k 的大作中提到】
: 结果对于我来说还是比较重要吧，比如从10*N 改进到0.1*N,这种情况下用O(N)表示就
: 显现不出差距了，但是事实上差距还是比较大。这种情况不用big O而是直接表示比较
: 合适？
|
a****9
发帖数: 418 | 17 这种就完全不要理big O了
直接plot 出来 给定一个N 别人需要多少空间 你用多少空间
只要你不是投的理论方向的会议, 都是perfect的
题中
人会
【在 s********k 的大作中提到】
: 结果对于我来说还是比较重要吧，比如从10*N 改进到0.1*N,这种情况下用O(N)表示就
: 显现不出差距了，但是事实上差距还是比较大。这种情况不用big O而是直接表示比较
: 合适？
|
w**********s
发帖数: 291 | 18 如果真是能够提高到一个数量级，那还是有实际意义的。
重要的找一个重要的concrete的application来突出你的贡献，不要泛泛地讨论空间复
杂度。
【在 s********k 的大作中提到】
: 结果对于我来说还是比较重要吧，比如从10*N 改进到0.1*N,这种情况下用O(N)表示就
: 显现不出差距了，但是事实上差距还是比较大。这种情况不用big O而是直接表示比较
: 合适？
|
s********k
发帖数: 6180 | 19 我这个不是理论的文章，就是针对application的文章，实际上效果确实好不少，现在是想把用理论分析加以说明。这样应该比在某个特定的实际系统上更有说服力。提高数量级最好就是直接表示而不是用big O之类的？
【在 w**********s 的大作中提到】
: 如果真是能够提高到一个数量级，那还是有实际意义的。
: 重要的找一个重要的concrete的application来突出你的贡献，不要泛泛地讨论空间复
: 杂度。
|
a***y
发帖数: 852 | 20 Give me your Email then I can send it to you
37M for pdf or
13M for djvu
【在 w**********s 的大作中提到】
: 空间复杂度也是算法的性能指标之一，只是不像时间复杂度一样重要，除非你的问题中
: ，存储是一个
: 极大的瓶颈。
: 要么你这个improvement比较significant，而且问题的存储背景够强，否则可能没人会
: 太关心你的结果。
|
Y*****y
发帖数: 361 | 21 同一个量级，只是改变系数，那就不要用big-O notation了吧……做理论的也有很多是
去close系数的。 |
