关于时间复杂度O(1), O(n), O(log n), O(n log n)的问题

Questions about Time complexity O(1), O(n), O(log n), O(n log n)

我目前正在研究 arraylist 的时间复杂度，尤其是关于访问和搜索的时间复杂度。我不太清楚哪个是哪个。

所以我知道访问的时间复杂度（当你知道索引时）是 O(1)。

但是 2 和 3 正确吗？？

arraylist排序后在arraylist上搜索，不知道index是O(n)...?
时间复杂度当你需要从未排序的arraylist中查找数据而你不知道它的索引是O(n)...?

2 和 3 的答案应该一样吗？或排序/未排序的数组列表会改变时间复杂度？

通过数组列表进行线性搜索时，您正在寻找某个元素。由于您不知道数据位于哪个索引，因此您必须遍历每个元素，直到找到您要查找的项目。

在最坏的情况下，你必须一直走到最后一个元素。 Big Oh 作为算法的上限。在最坏的情况下，我们必须遍历所有 n 个元素，所以算法是 O(n).

如果 arraylist 已排序，您可以使用 O(log n) 的二进制搜索

对于 #2，这取决于您进行搜索的方式。如果您进行顺序搜索，例如使用 indexOf(Object o)，那么无论数据是否排序，性能都是 O(n)。

搜索 排序的 列表或数组可以在 O(log n) 中完成使用 二进制搜索算法。

正在对 List can be done using Collections.binarySearch() 进行二进制搜索。正如 javadoc 所说：

This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.

可以使用 Arrays.binarySearch().

对数组进行二分查找

关于时间复杂度O(1), O(n), O(log n), O(n log n)的问题

Questions about Time complexity O(1), O(n), O(log n), O(n log n)

java

arraylist

time-complexity