O(N) 是什么意思
可能的重复：
什么是 Big O 表示法？你用过吗？
大家好，这是
一个相当基本的可扩展性符号问题。
我最近收到一篇关于我的 python 有序列表实现的帖子的评论 “但要注意，你的‘有序集’实现对于插入来说是 O(N) ”
这很高兴知道，但我不确定这意味着什么。
我见过 n(o) o(N)、N(o-1) 或 N(o*o) 等符号，
上面的符号指的是什么？
Possible Duplicate:
What is Big O notation? Do you use it?
Hi all,
fairly basic scalability notation question.
I recently recieved a comment on a post that my python ordered-list implimentation
"but beware that your 'ordered set' implementation is O(N) for insertions"
Which is great to know, but I'm not sure what this means.
I've seen notation such as n(o) o(N), N(o-1) or N(o*o)
what does the above notation refer to?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
该评论引用了 Big-O 表示法。
简而言之：
与项目数量无关。
项目数量。
log(N)
基本上任何“O”表示法都意味着操作最多需要 k*f(N)
在哪里：
The comment was referring to the Big-O Notation.
Briefly:
independent of the number of items.
number of items.
log(N)
Basically any 'O' notation means an operation will take time up to a maximum of k*f(N)
where:
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 相同的速率增长。
O(n) is Big O Notation and refers to the complexity of a given algorithm. n refers to the size of the input, in your case it's the number of items in your list.
O(n) means that your algorithm will take on the order of n operations to insert an item. e.g. looping through the list once (or a constant number of times such as twice or only looping through half).
O(1) means it takes a constant time, that it is not dependent on how many items are in the list.
O(n^2) means that for every insert, it takes n*n operations. i.e. 1 operation for 1 item, 4 operations for 2 items, 9 operations for 3 items. As you can see, O(n^2) algorithms become inefficient for handling large number of items.
For lists O(n) is not bad for insertion, but not the quickest. Also note that O(n/2) is considered as being the same as O(n) because they both grow at the same rate with n.
它被称为大 O 表示法： http://en.wikipedia.org/wiki/Big_O_notation
这么说插入是
O(n)意味着您必须遍历整个列表（或其中一半 - 大 O 表示法忽略常量因子）才能执行插入。这看起来是一个很好的介绍： http:// /rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
It's called Big O Notation: http://en.wikipedia.org/wiki/Big_O_notation
So saying that insertion is
O(n)means that you have to walk through the whole list (or half of it -- big O notation ignores constant factors) to perform the insertion.This looks like a nice introduction: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
它指的是你的程序有多复杂，即实际解决一个问题需要多少次操作。 O(n) 意味着每个操作都需要与列表中的项目相同的步骤数，这对于插入来说非常慢。同样，如果您有 O(n^2) 意味着任何操作都需要“n”平方数才能完成，依此类推...“O”表示数量级，括号中的表达式是始终与过程中操作的项目数量相关。
It refers to how complex your program is, i.e., how many operations it takes to actually solve a problem. O(n) means that each operation takes the same number of steps as the items in your list, which for insertion, is very slow. Likewise, if you have O(n^2) means that any operation takes "n" squared number of steps to accomplish, and so on... The "O" is for Order of Magnitude, and the the expression in the parentheses is always related to the number of items being manipulated in the procedure.
具体来说，O(n) 意味着如果列表中的项目数量是 2 倍，则需要 不超过 两倍的时间，如果列表中的项目数量是 50 倍的话。所需时间不超过 50 倍。有关更多详细信息，请参阅维基百科文章 dreeves 指出
编辑（上面以粗体显示）：有人指出 Big-O 确实代表上限，因此如果列表中的元素数量是两倍，则插入将在 most 两倍长，如果有 50 倍的元素，则最多需要 50 倍的时间。
如果另外是 Ω(n)（n 的大欧米茄），那么对于两倍大的列表来说，至少需要两倍的时间。如果您的实现既是 O(n) 又是 Ω(n)，这意味着对于两倍大的列表，至少需要两倍的长度和最多两倍的长度，那么可以说是 θ(n)（n 的 Big Theta），这意味着如果元素数量是两倍，则需要的时间恰好是两倍。
根据维基百科（以及个人经验，我自己也对此感到内疚），Big-O 经常用于 Big-Theta 的含义。从技术上讲，调用您的函数 O(n^n^n^n) 是正确的，因为所有 Big-O 都说您的函数不比这慢，但除了证明一点之外，没有人会真正这么说，因为它是尽管技术上准确，但不是非常有用且具有误导性的信息。
Specifically O(n) means that if there's 2x as many items in the list, it'll takes No more than twice as long, if there's 50 times as many it'll take No more than 50 times as long. See the wikipedia article dreeves pointed out for more details
Edit (in bold above): It was pointed out that Big-O does represent the upper bound, so if there's twice as many elements in the list, insertion will take at most twice as long, and if there's 50 times as many elements, it would take at most 50 times as long.
If it was additionally Ω(n) (Big Omega of n) then it would take at least twice as long for a list that is twice as big. If your implementation is both O(n) and Ω(n), meaning that it'll take both at least and at most twice as long for a list twice as big, then it can be said to be Θ(n) (Big Theta of n), meaning that it'll take exactly twice as long if there are twice as many elements.
According to Wikipedia (and personal experience, being guilty of it myself) Big-O is often used where Big-Theta is what is meant. It would be technically correct to call your function O(n^n^n^n) because all Big-O says is that your function is no slower than that, but no one would actually say that other than to prove a point because it's not very useful and misleading information, despite it being technically accurate.
简短回答：这意味着处理时间与输入大小成线性关系。例如，如果输入的大小（列表的长度）增加三倍，则处理时间（大约）增加三倍。如果增加千倍，处理时间也会以同样的幅度增加。
长答案：请参阅 Ian P 和 dreeves 提供的链接
Short answer: It means that the processing time is in linear relation to the size of input. E.g if the size of input (length of list) triples, the processing time (roughly) triples. And if it increases thousandfold, the processing time also increases in the same magnitude.
Long answer: See the links provided by Ian P and dreeves
这可能会有所帮助：
http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
祝你好运！
This may help:
http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
Good luck!
维基百科的解释比我好得多，但这意味着如果你的列表大小是N，插入一个项目最多需要 N 次循环/迭代。 （实际上，您必须迭代整个列表）
如果您想更好地理解，有一本免费的书 来自伯克利，对符号进行了更深入的了解。
Wikipedia explains it far better than I can, however it means that if your list size is N, it takes at max N loops/iterations to insert an item. (In effect, you have to iterate over the whole list)
If you want a better understanding, there is a free book from Berkeley that goes more in-depth about the notation.