Java中Arrays.stream()的时间复杂度是O(n)还是O(n log n)？

首先直接给结论：Arrays.stream() 方法本身的创建时间复杂度是 O(1)，如果算上遍历整个流完成终端操作的整体开销，时间复杂度是 O(n)，完全不存在O(n log n)的成本。你产生这个疑问，核心是把「流的天然有序属性」和「排序操作的开销」混淆了。

先回到官方文档的描述：

部分流数据源（例如List或arrays）是天然有序的，而另一些流数据源（例如HashSet）不具备天然有序特性。

这里说的「天然有序」，指的是数据源本身已经有固定的元素遍历顺序，不需要流在创建阶段做任何额外排序处理：

• 数组本身是连续内存存储的结构，元素的访问顺序天生由下标决定，这个顺序是存储结构自带的属性，不需要任何计算来维护。
• Arrays.stream() 的实现逻辑非常轻量，只是把传入的数组包装成一个流对象，内部直接持有原数组的引用，既不会复制数组元素，也不会做任何排序处理，创建流的过程几乎没有额外成本。

关于你提到的O(n log n)开销，只有一种场景会出现：你主动在流管道中调用了sorted()中间操作，这时候不管数据源本身是不是有序，都会触发排序逻辑产生对应开销。反过来，只要你不主动调用排序相关方法，哪怕是无序的HashSet生成的流，也不会凭空产生排序成本。

你可以用最朴素的逻辑验证：普通for循环按下标遍历数组的时候，没人会觉得这个循环的时间复杂度是O(n log n)——毕竟数组本来就是按下标固定顺序存储的，直接顺着读就行。Arrays.stream()返回的有序流，遍历逻辑和普通for循环没有本质区别，只是把遍历逻辑包装成了流的管道操作，自然不会凭空多出排序的额外开销。

内容的提问来源于stack exchange，提问作者Neha Jain