Java ArrayList 的 indexOf 复杂度是 N 吗？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21388466/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is ArrayList indexOf complexity N?
提问by good_evening
I have N numbers in arraylist. To get the indexOf, arraylist will have to iterate maximum N times, so complexity is O(N), is that correct?
我在数组列表中有 N 个数字。为了得到indexOf，arraylist 必须最多迭代 N 次，所以复杂度是O(N)，对吗？
回答by Tim B
Yes, that is correct. The order is based off the worst case.
对，那是正确的。该订单基于最坏的情况。
回答by Hong Wei Wang
100%, it needs to iterate through the list to find the correct index.
100%，它需要遍历列表以找到正确的索引。
回答by Nambi
Source Java API
Yes,Complexity is O(N).
是的，复杂度是 O(N)。
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
size、isEmpty、get、set、iterator 和 listIterator 操作在恒定时间内运行。add 操作在分摊常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都在线性时间内运行（粗略地说）。与 LinkedList 实现相比，常量因子较低。
回答by Dakkaron
It is true. Best Case is 1 so O(1), Average Case is N/2 so O(N) and Worst Case is N so O(N)
是真的。最佳情况是 1，所以 O(1)，平均情况是 N/2，所以 O(N) 和最坏情况是 N，所以 O(N)
回答by Roudy Tarabay
An ArrayList is an Array with more features. So the order of complexity for operations done to an ArrayList is the same as for an Array.
ArrayList 是具有更多功能的数组。因此对 ArrayList 执行的操作的复杂性顺序与 Array 相同。
回答by Daniel Imms
Yes it's O(n)as it needs to iterate through every item in the list in the worst case.
是的，它是O(n)，因为在最坏的情况下它需要遍历列表中的每个项目。
The only way to achieve better than this is to have some sort of structure to the list. The most typical example being looking through a sorted list using binary search in O(log n)time.
实现比这更好的唯一方法是为列表添加某种结构。最典型的例子是在O(log n)时间内使用二进制搜索查看排序列表。
回答by Lajos Arpad
In the worst case you find the element at the very last position, which takes N steps, that is, O(N). In the best case the item you are searching for is the very first one, so the complexity is O(1). The average length is of the average number of steps. If we do not have further context, then this is how one can make the calculations:
在最坏的情况下，您会在最后一个位置找到元素，这需要 N 步，即 O(N)。在最好的情况下，您要搜索的项目是第一个项目，因此复杂度为 O(1)。平均长度是平均步数。如果我们没有进一步的上下文，那么我们可以这样进行计算：
avg = (1 + 2 + ... n) / n = (n * (n + 1) / 2) / n = (n + 1) / 2
avg = (1 + 2 + ... n) / n = (n * (n + 1) / 2) / n = (n + 1) / 2
If n -> infinity, then adding a positive constant and dividing by a positive constant has no effect, we still have infinity, so it is O(n).
如果n -> infinity，那么加上一个正常数并除以一个正常数没有效果，我们仍然有无穷大，所以它是 O(n)。
However if you have a large finite data to work with, then you might want to calculate the exact average value as above.
但是，如果您有大量的有限数据要处理，那么您可能需要按上述方法计算精确的平均值。
Also, you might have a context there which could aid you to get further accuracy in your calculations.
此外，您可能有一个上下文可以帮助您在计算中获得更高的准确性。
Example:
例子：
Let's consider the example when your array is ordered by usage frequency descendingly. In case that your call of indexOfis a usage, then the most probable item is the first one, then the second and so on. If you have exact usage frequency for each item, then you will be able to calculate a probable wait time.
让我们考虑一下当您的数组按使用频率降序排列时的示例。如果您的调用indexOf是一个用法，那么最可能的项目是第一个，然后是第二个，依此类推。如果您有每个项目的确切使用频率，那么您将能够计算出可能的等待时间。
