时间复杂性用大O还是大theta更合适？为什么？

2019/3/3镜像同步10 回复

求解惑。。搜了一波，看到： "In some fields, however, the big O notation (number 2 in the lists above) would be used more commonly than the Big Theta notation (bullets number 3 in the lists above). For example, if T(n) represents the running time of a newly developed algorithm for input size n, the inventors and users of the algorithm might be more inclined to put an upper asymptotic bound on how long it will take to run without making an explicit statement about the lower asymptotic bound." 但觉得根本没有说到点上。。明明theta更准确啊。

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

chl机器人#1 · 2019/3/4

大O好算啊

hezhiqi734机器人#2 · 2019/3/4

的确是大theta的说法更准确，但是大家现在都约定俗成地把大theta的意思套在大O上面用了。除了考试，写大O不会有啥问题个人觉得，大O流行起来的原因是比较好输入，你看这么半天我们都没把Theta打出来过

rancho机器人#3 · 2019/3/4

Θ-Θ 用这个符号表示时间复杂度，会不会给人一种在时间上很长很久的感觉。

lance6716机器人#4 · 2019/3/4

又到了安利算法导论的时候了

yo1995机器人#5 · 2019/3/4

哈哈ωΩΘOo[em3]

mqweo机器人#6 · 2019/3/4

大O是上界,大Omega是下界,这两组合起来后是大Theta(精确界)... 个人觉得严格来说大O是不精确的,但已经广泛使用了. 下面是参考: 人们有时会假设O记号给出了精确的增长的阶,从而过度使用它,他们用它就好像它既给出了下界又给出了上界.例如,对n个数进行排序的算法可以称为是无效的,"因为它的运行时间是O(n^2)."但是运行时间O(n^2)并不意味着运行时间不可以是O(n).[具体数学中文第2版P374最后一段] People sometimes abuse O-notation by assuming that it gives an exact order of growth; they use it as if it specifies a lower bound as well as an upper bound. For example, an algorithm to sort n numbers might be called ineffcient "because its running time is O(n^2 )." But a running time of O(n^2 ) does not imply that the running time is not also O(n).[此书英文原话]

Cap机器人#7 · 2019/3/4

很多时候我们只关心上界，没有问题。当然，要证明这是最优算法的时候，可能同时也要关心一下下界。

w350053002机器人#8 · 2019/3/4

理论上有的算法复杂度会针对不同数据有很不一样的表现嘛，然后O就表示在各种数据下可能有的最糟糕的表现。。话说这种情况是不是就没法用theta表示的。。maybe

lucashood机器人#9 · 2019/3/4

这也能膜【在 rancho (意涵团不遗憾！) 的大作中提到: 】 : Θ-Θ : 用这个符号表示时间复杂度，会不会给人一种在时间上很长很久的感觉。