如何对使用JDK streams API的代码进行渐近分析?

这个代码的Big-O分析是什么?

• 没有理由认为 Arrays.stream() 它本身会随着问题的大小而扩展。
• Stream.forEach() n K ,在哪里 n 是数组的大小 K 是lambda的渐近复杂性。您的特定使用不会缩短迭代,因此没有理由期望更严格的限制
• lambda的复杂性是由 Collections.frequency() n

总的来说,这就是O( n ).

这里的浪费是扫描整个集合中的每个数组元素。因为每个值平均要出现1000次,所以这是非常昂贵的,而且它会随着数组元素的数量而扩展。我怀疑你打算只扫描一次 count

array (大小100000),而您所需要做的只是在您创建的列表中查找数字0到100的频率(假设为独占),因此有效地迭代100次,如下所示:

int[] counts = new int[100];
IntStream.range(0,100).forEach(i -> counts[i] = Collections.frequency(l,i));

int[] counts = new int[100];
for( int i = 0 ; i < array.length ; i ++){
    counts[array[i]]++; // same asssumption (array[i] < 100)
}

或者用溪流来表示

Arrays.stream(array).forEach(i -> counts[i]++);