java - Arrays.copyOfRange() 的运行时

Question

Java 的 Arrays.copyOfRange(array, startIndex, endIndex) 函数的大 O 运行时是什么？

例如，就空间和时间复杂度而言，使用 copyOfRange 编写一个简单的数组函数二分搜索而不是传入开始和结束索引是否等效或效率更低？

Answer 1

Arrays.copyRangeOf()使用 System.arraycopy()它在后台使用 native 代码(例如可以使用 memcpy - 取决于 JIT 实现)。

使用 System.arraycopy() 进行复制的“魔力”是通过一次调用来复制一 block 内存，而不是进行 n 次不同的调用。

这意味着与您选择自己实现的任何其他解决方案相比，使用 Arrays.copyOfRange() 肯定会更有效。

此外，我看不出二分搜索在这里有何帮助:数组可以直接访问 - 现在我们确切地知道 src、dst 是什么以及我们应该复制多少项。

从大 O 的角度来看，复杂度将为 O(n*k)，其中 n 是要复制的项目数，k 是每个项目的大小(以位为单位)。空间复杂度相同。