Fir*_*row 45 performance big-o scalability set
可能重复:
什么是Big O表示法？你用它吗？
大家好,
相当基本的可扩展性符号问题.
我最近收到了一篇关于我的python有序列表实现的帖子的评论"但要注意你的'有序集'实现是插入的O(N)"
很高兴知道,但我不确定这意味着什么.
我看过n(o)o(N),N(o-1)或N(o*o)等符号
上述符号是指什么？
qua*_*ana 58
该评论指的是Big-O表示法.
简述:
基本上任何'O'符号表示操作需要时间最多为k*f(N)
,其中:
k是常数乘数
f()是一个依赖于N的函数
dre*_*ves 23
它被称为Big O Notation:http: //en.wikipedia.org/wiki/Big_O_notation
所以说插入O(n)意味着你必须遍历整个列表(或其中一半 - 大O符号忽略常数因素)来执行插入.
这看起来很不错:http : //rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
Col*_*son 15
O(n)是Big O表示法,指的是给定算法的复杂性.n表示输入的大小,在您的情况下,它是列表中的项目数.
O(n)表示您的算法将采用n次操作的顺序来插入项目.例如,循环遍历列表一次(或常数次,例如两次或仅循环一半).
O(1)表示它需要一个恒定的时间,它不依赖于列表中有多少项.
O(n ^ 2)表示对于每个插入,它需要n*n次操作.即1项操作1项,2项4项操作,3项9项操作.如您所见,O(n ^ 2)算法在处理大量项目时效率低下.
对于列表,O(n)对于插入来说并不坏,但不是最快的.还要注意O(n/2)被认为与O(n)相同,因为它们都以与n相同的速率增长.
Dav*_*vy8 11
特别是O(n)意味着如果列表中的项目数量是2 倍,那么它将花费不超过两倍的时间,如果它需要50倍的时间,则不会 超过 50倍.有关详细信息,请参阅维基百科文章dreeves指出
编辑(粗体以上):有人指出,大O确实代表了上限,所以如果有两次在列表中的许多元素,插入将在最两倍长的时间,如果有50倍,许多元素,它最多需要 50倍.
如果它另外是Ω(n)(n的大欧米茄)那么对于大于两倍的列表,它将花费至少两倍的时间.如果你的实现是同时为O(n)和Ω(N),这意味着它会在采取两种至少在最两倍长的名单两倍大,那么就可以说是Θ(N)(大n)的θ,意味着如果有两倍的元素,它将花费两倍的时间.
根据维基百科(以及个人经验,我自己也有罪),Big-O通常用于Big-Theta的含义.这将是技术上是正确的打电话给你的函数O(n ^ N ^ N ^ N),因为所有大O说的是,你的功能并不比慢,但没有人会真正要说的是,除了想证明一点,因为它是虽然它在技术上是准确的,但不是非常有用和误导性的信息.
它指的是您的程序有多复杂,即实际解决问题需要多少操作.O(n)表示每个操作采用与列表中的项目相同的步骤数,这些项目的插入速度非常慢.同样,如果你有O(N ^ 2)是指进行任何操作"N"的步骤平方数来完成,等等......的"O"是数量级,并在括号中的表达式为始终与过程中操作的项目数相关.
| 归档时间： |
|
| 查看次数： |
57116 次 |
| 最近记录： |