你了解大O符号(big-O notation)么？你能给出不_

金玉峰

大O符号是描述数据结构里面元素增加的时候，数据的规模或者是一个渐进上界。它还可以描述其它的行为，比如内存消耗。集合类实际上也是数据结构，可以利用大O符号基于时间、内存和性能选择最好的方式。大O符号可以对大量数据的性能有一个很好的说明

编辑于 2018-05-04 08:42:13 回复(0)

zll

大O符号表示一个程序运行时所需要的渐进时间复杂度上界。

其函数表示是：

对于函数f(n),g(n),如果存在一个常数c，使得f(n)<=c*g(n),则f(n)=O(g(n));

大O描述当数据结构中的元素增加时，算法的规模和性能在最坏情景下有多好。

大O还可以描述其它行为，比如内存消耗。因为集合类实际上是数据结构，因此我们一般使用大O符号基于时间，内存，性能选择最好的实现。大O符号可以对大量数据性能给予一个很好的说明。

发表于 2016-03-19 20:07:40 回复(2)

润X

O：大O是上界

Θ：大Θ是平均值

Ω：大Ω是下界

发表于 2017-03-27 14:23:35 回复(0)

装逼小王子

O表示算法的时间或者空间复杂度上界。比如数组的插入时间复杂度为O(N),空间复杂度为O(1),链表的插入时间复杂度为O(1),空间复杂度为O(1).

发表于 2017-07-30 15:35:34 回复(0)

丸子one

时间和空间复杂度上界

发表于 2017-10-01 20:06:00 回复(0)

💯somEoNE

$\Theta (g(n)) = \{f(n) :$ there exist positive constants $c_1, c_2$ , and $n_0$ such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0\}$

$O (g(n)) = \{f(n) :$ there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq cg(n)$ for all $n \geq n_0\}$

$\Omega (g(n)) = \{f(n) :$ there exist positive constants $c$ and $n_0$ such that $0 \leq cg(n) \leq f(n)$ for all $n \geq n_0\}$

from "Introduction to Algorithms"

发表于 2019-03-24 16:18:28 回复(0)

花谢「花开

渐近上届，时间或内存，在规模达到一定程度后，接近一个值，用来描述算法的性能

发表于 2019-03-19 15:13:40 回复(0)

steaf

大O符号描述了当数据结构里面的元素增加的时候，算法的规模或者是性能在最坏的场景下有多么好。大O符号也可用来描述其他的行为，比如：内存消耗。因为集合类实际上是数据结构，我们一般使用大O符号基于时间，内存和性能来选择最好的实现。大O符号可以对大量数据的性能给出一个很好的说明。

发表于 2016-03-10 11:54:35 回复(0)

西弗斯

大O符号描述了党数据结构里面的元素增加的时候，算法的规模或者是性能在最坏的场景下有多么好。

大O符号也可以用来描述其他的行为，比如：内存消耗。因为集合类实际上是数据结构，我们一般使用大O富豪基于时间，内存和性能来选择最好的实现。大O富豪可以对大量数据的性能给出一个很好的说明。

发表于 2016-03-17 22:12:30 回复(0)

牛客牛牛气冲天

大O符号描述了当数据结构里面的元素增加的时候，算法的规模或者是一个渐进上界。大O符号也可用来描述其他的行为，比如：内存消耗。因为集合类实际上是数据结构，我们一般使用大O符号基于时间，内存和性能来选择最好的实现。大O符号可以对大量数据的性能给出一个很好的说明。

O：大O是上界
Θ：大Θ是平均值
Ω：大Ω是下界
O表示算法的时间或者空间复杂度上界。比如数组的插入时间复杂度为O(N),空间复杂度为O(1),链表的插入时间复杂度为O(1),空间复杂度为O(1).

发表于 2021-08-14 00:55:24 回复(0)