Java 的 ArrayList.sublist(startIndex, endIndex) 方法的时间复杂度是多少? [英] What is the time complexity of Java's ArrayList.sublist(startIndex, endIndex) method?

问题描述

这个问题基本上说明了一切.假设我有一个(排序的)列表，可以包含 1K 到 1M 的任何项目.我有一个 starting index 和一个 ending index.如果我使用 ArrayList.sublist(start, end) 方法，时间复杂度是 O(n) 还是 O(1)?我确实在这里检查了答案，因为我认为这是一个常见问题，但是虽然我找到了 LinkedList 的重复答案，但我找不到关于 ArrayList 的具体问题.感谢大家的回答！

The question basically says it all. Suppose I have a (sorted) list that can contain anywhere from 1K to 1M items. I have a starting index and an ending index. If I use the ArrayList.sublist(start, end) method, is the time complexity O(n) or O(1)? I did check for answers here since I'd think would be a common question, but although I found a duplicate answer for a LinkedList, I couldn't find a specific question about ArrayList. Thanks to all for their answers!

推荐答案

子列表由源列表支持.没有复制步骤，所以时间复杂度是O(1).

The sub-list is backed by the source list. There is no copy step, so the time complexity is O(1).

这篇关于Java 的 ArrayList.sublist(startIndex, endIndex) 方法的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！