将元素移动到第一位时，ArrayList 与 LinkedList 的复杂性

Question

我想分析使用 LinkedList 或 ArrayList 将 1 2 3 4 移动到 3 1 2 4（整数列表）。

我做了什么：

aux = arraylist.get(2); // O(1)
arraylist.remove(2); // O(n)
arraylist.add(0, aux); // O(n), shifting elements up.

aux = linkedlist.get(2); // O(n)
linkedlist.remove(2); // O(n)
linkedlist.addFirst(aux); // O(1)

所以，在这种情况下，我们可以说它们是相同的还是我遗漏了什么？

Answer 1

这是一个快速而粗略的基准测试。我为这两个操作计时并重复了一百万次：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {

    public static void main(String[] args) {
        int arrayListTime = 0;
        int linkedListTime = 0;
        int n = 10000000;
        for (int i=0; i<n; i++) {
            ArrayList<Integer> A = new ArrayList<>(Arrays.asList(1,2,3,4));
            long startTime = System.currentTimeMillis();
            int x = A.remove(2);
            A.add(0, x);
            long endTime = System.currentTimeMillis();
            arrayListTime += (endTime - startTime);

            LinkedList<Integer> L = new LinkedList<>(Arrays.asList(1,2,3,4));
            long startTime2 = System.currentTimeMillis();
            int x2 = L.remove(2);
            L.addFirst(x2);
            long endTime2 = System.currentTimeMillis();
            linkedListTime += (endTime2 - startTime2);
        }

        System.out.println(arrayListTime);
        System.out.println(linkedListTime);
    }
}

差别很小。我的输出是：

424
363

因此，在 1,000,000 次操作过程中，使用 LinkedList 仅快 61 毫秒。

Answer 2

当输入非常小时，大 O 复杂性毫无意义，就像您的情况一样。回想一下，大 O 的定义只适用于 "large enough n"，我怀疑你是否已经达到 n==4 的阈值。

如果这在一个小数据量的紧密循环中运行（并且每次都有不同的数据），唯一真正重要的是缓存性能，并且数组列表解决方案比缓存更友好链表解决方案，因为链表中的每个 Node 都可能需要缓存查找。
在这种情况下，我什至更喜欢使用原始数组 (int[])，以避免冗余包装对象，这会触发更多缓存未命中。

Answer 3

你确实可以说这个特定操作对 LinkedList 和 ArrayList 都需要 O(n) 时间。

但是你不能说他们因此而占用了相同的实时时间。

Big-O 符号仅告诉您运行时间将如何随着输入变大而缩放，因为它忽略了常数因子。因此，一个 O(n) 算法最多可以进行 1*n 次操作或 100000*n 次操作或更多操作，并且这些操作中的每一个所花费的时间可能相差很大。这也意味着它通常是一个非常不准确的小输入性能度量，因为常数因子对运行时间的影响比小输入的大小更大（但性能差异对于小输入往往不太重要).

另请参阅：What is a plain English explanation of "Big O" notation?

将元素移动到第一位时，ArrayList 与 LinkedList 的复杂性

ArrayList vs LinkedList complexity when moving element to the first place

java

algorithm

complexity-theory

linked-list

arraylist