Dart 中 dart List.insert 的时间复杂度是多少？

Question

根据我对 Dart 中列表的理解，它们的行为似乎类似于 C++ 中的向量。所以，假设，如果我要在列表的开头插入一个元素，它将把剩余的元素移出，导致时间复杂度为 O(列表的长度)。有人可以确认这是否是有效的吗？

final numbers = <int>[1, 2, 3, 4];
const index = 0;
numbers.insert(index, 10);
print(numbers); // [10, 1, 2, 3, 4]

Answer 1

试试这个飞镖代码：

void measureInsertAndAddTime(int size) {
  List<int> testList = List.generate(size, (index) => index);

  Stopwatch addStopwatch = new Stopwatch()..start();
  testList.add(0);
  print('add done in ${addStopwatch.elapsed}');

  Stopwatch insertstopwatch = new Stopwatch()..start();
  testList.insert(0, 0);
  print('insert done in ${insertstopwatch.elapsed}');
}

void main() {
  for (int i = 10; i <= 100000000; i *= 10) {
    print("for list of size: $i");
    measureInsertAndAddTime(i);
  }
}

这是我的执行结果：

for list of size: 10
add done in 0:00:00.000343
insert done in 0:00:00.000245
for list of size: 100
add done in 0:00:00.000001
insert done in 0:00:00.000010
for list of size: 1000
add done in 0:00:00.000001
insert done in 0:00:00.000056
for list of size: 10000
add done in 0:00:00.000001
insert done in 0:00:00.000627
for list of size: 100000
add done in 0:00:00.000010
insert done in 0:00:00.002558
for list of size: 1000000
add done in 0:00:00.000004
insert done in 0:00:00.013539
for list of size: 10000000
add done in 0:00:00.000004
insert done in 0:00:00.116381
for list of size: 100000000
add done in 0:00:00.000005
insert done in 0:00:01.184865

如您所见，add函数的复杂度为 O(1)。对于所有不同的列表大小都是恒定的。但该insert函数似乎有 O(n) 。如果它的行为像向量，它必须保持不变。所以我认为情况insert实际上正在发生变化。