System.arraycopy（…）的时间复杂度？

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)是一种本机方法。

这种方法的时间复杂度是多少？

Answer 1

它必须遍历数组中的所有元素才能执行此操作。 Array是一种独特的数据结构，您必须在初始化时指定大小。 顺序是源数组的大小，或者在大O项中是O（长度）。

事实上，这发生在ArrayList内部。 ArrayList包装一个数组。 虽然ArrayList看起来像一个动态增长的集合，但在内部它必须扩展时才进行arrycopy。

Answer 2

我做了一些调查后来决定写一个测试代码，这就是我所拥有的。

我的测试代码如下：

 import org.junit.Test; public class ArrayCopyTest { @Test public void testCopy() { for (int count = 0; count < 3; count++) { int size = 0x00ffffff; long start, end; Integer[] integers = new Integer[size]; Integer[] loopCopy = new Integer[size]; Integer[] systemCopy = new Integer[size]; for (int i = 0; i < size; i++) { integers[i] = i; } start = System.currentTimeMillis(); for (int i = 0; i < size; i++) { loopCopy[i] = integers[i]; } end = System.currentTimeMillis(); System.out.println("for loop: " + (end - start)); start = System.currentTimeMillis(); System.arraycopy(integers, 0, systemCopy, 0, size); end = System.currentTimeMillis(); System.out.println("System.arrayCopy: " + (end - start)); } } } 

它产生如下所示的结果

 for loop: 47 System.arrayCopy: 24 for loop: 31 System.arrayCopy: 22 for loop: 36 System.arrayCopy: 22 

所以，Bragboy是正确的。

Answer 3

只是总结另一个问题的相关评论（标记为此问题的副本）。

当然，它只是添加到另一个的所有条目的新arrays？ 哪个是O（n） ，其中n是要添加的值的数量。

当然bragboy的回答是一致的，但后来我认为获得肯定答案的唯一方法是找到源代码来获得规范的答案 ，但这是不可能的。 这是System.arraycopy();的声明System.arraycopy();

 public static native void arraycopy(Object src, int src_position, Object dst, int dst_position, int length); 

它是native ，用操作系统的语言编写，这意味着arraycopy()的实现依赖于平台。

所以，总的来说它可能是O（n） ，但也许不是。

Answer 4

以下是OpenJDK 8的一些相关源代码（openjdk-8-src-b132-03_mar_2014）。 我在Java本机方法源代码的帮助下找到了它（注意：说明令人困惑;我只是搜索了相关标识符的来源）。 我认为福特船长的评论是正确的; 即，存在（许多）不需要迭代每个元素的情况。 请注意，不迭代每个元素并不一定意味着O（1），它只是意味着“更快”。 我认为 ，无论如何，数组副本必须基本上是O（x），即使x不是数组中的项数; 也就是说，无论如何，复制在数组中使用更多元素会变得更加昂贵，如果你有一个非常大的数组，它将需要线性长时间。 警告：我不确定这是您正在运行的Java的实际源代码; 只是这是我在OpenJDK 8源代码中找到的唯一实现。 我认为这是一个跨平台的实现，但我可能错了 – 我当然没有想出如何构建这个代码。 另请参见： Oracle JDK和Open JDK之间的差异 。 以下来自：/openjdk/hotspot/src/share/vm/oops/objArrayKlass.cpp

 // Either oop or narrowOop depending on UseCompressedOops. template  void ObjArrayKlass::do_copy(arrayOop s, T* src, arrayOop d, T* dst, int length, TRAPS) { BarrierSet* bs = Universe::heap()->barrier_set(); // For performance reasons, we assume we are that the write barrier we // are using has optimized modes for arrays of references. At least one // of the asserts below will fail if this is not the case. assert(bs->has_write_ref_array_opt(), "Barrier set must have ref array opt"); assert(bs->has_write_ref_array_pre_opt(), "For pre-barrier as well."); if (s == d) { // since source and destination are equal we do not need conversion checks. assert(length > 0, "sanity check"); bs->write_ref_array_pre(dst, length); Copy::conjoint_oops_atomic(src, dst, length); } else { // We have to make sure all elements conform to the destination array Klass* bound = ObjArrayKlass::cast(d->klass())->element_klass(); Klass* stype = ObjArrayKlass::cast(s->klass())->element_klass(); if (stype == bound || stype->is_subtype_of(bound)) { // elements are guaranteed to be subtypes, so no check necessary bs->write_ref_array_pre(dst, length); Copy::conjoint_oops_atomic(src, dst, length); } else { // slow case: need individual subtype checks // note: don't use obj_at_put below because it includes a redundant store check T* from = src; T* end = from + length; for (T* p = dst; from < end; from++, p++) { // XXX this is going to be slow. T element = *from; // even slower now bool element_is_null = oopDesc::is_null(element); oop new_val = element_is_null ? oop(NULL) : oopDesc::decode_heap_oop_not_null(element); if (element_is_null || (new_val->klass())->is_subtype_of(bound)) { bs->write_ref_field_pre(p, new_val); *p = *from; } else { // We must do a barrier to cover the partial copy. const size_t pd = pointer_delta(p, dst, (size_t)heapOopSize); // pointer delta is scaled to number of elements (length field in // objArrayOop) which we assume is 32 bit. assert(pd == (size_t)(int)pd, "length field overflow"); bs->write_ref_array((HeapWord*)dst, pd); THROW(vmSymbols::java_lang_ArrayStoreException()); return; } } } } bs->write_ref_array((HeapWord*)dst, length); } 

Answer 5

我不明白Kowser的答案如何回答他自己的问题。 我想检查算法的时间复杂度你必须比较不同大小的输入的运行时间，如下所示：

 import org.junit.Test; public class ArrayCopyTest { @Test public void testCopy() { int size = 5000000; for (int count = 0; count < 5; count++) { size = size * 2; long start, end; Integer[] integers = new Integer[size]; Integer[] systemCopy = new Integer[size]; start = System.currentTimeMillis(); System.arraycopy(integers, 0, systemCopy, 0, size); end = System.currentTimeMillis(); System.out.println(end - start); } } } 

输出：

 10 22 42 87 147