我目前正在研究arraylist的时间复杂性，特别是关于访问和搜索。我不知道哪一个是哪一个。
所以我知道访问的时间复杂度（当你知道索引时）是o（1）。
但是2和3是正确的吗？？
当arraylist排序后，您不知道索引是o（n）…在arraylist上搜索。。。？
当您需要从未排序的arraylist中查找数据而不知道其索引是o（n）…时的时间复杂性。。。？
2和3的答案应该相同吗？或者排序/未排序的arraylist会改变时间复杂度？
我目前正在研究arraylist的时间复杂性，特别是关于访问和搜索。我不知道哪一个是哪一个。
所以我知道访问的时间复杂度（当你知道索引时）是o（1）。
但是2和3是正确的吗？？
当arraylist排序后，您不知道索引是o（n）…在arraylist上搜索。。。？
当您需要从未排序的arraylist中查找数据而不知道其索引是o（n）…时的时间复杂性。。。？
2和3的答案应该相同吗？或者排序/未排序的arraylist会改变时间复杂度？
2条答案
按热度按时间6bc51xsx1#
当在arraylist中进行线性搜索时，您正在查找某个元素。因为您不知道数据的索引是什么，所以必须遍历每个元素，直到找到要查找的项。
在最坏的情况下，你必须一直走到最后一个元素。big-oh作为算法的上界。在最坏的情况下，我们必须遍历所有n个元素，所以算法是o（n）。
如果arraylist已排序，则可以使用二进制搜索，即o（logn）
gwbalxhn2#
对于#2，这取决于你如何进行搜索。如果进行顺序搜索，例如使用
indexOf(Object o)，则无论数据是否排序，性能都为o（n）。使用二进制搜索算法，可以在o（logn）中搜索已排序的列表或数组。
对一个
List可以使用Collections.binarySearch(). 正如javadoc所说：对于“随机访问”列表（提供接近恒定时间的位置访问），此方法以log（n）时间运行。如果指定的列表未实现
RandomAccess这个方法将执行基于迭代器的二进制搜索，执行o（n）个链接遍历和o（logn）个元素比较。对数组执行二进制搜索可以使用
Arrays.binarySearch().