java - 为什么这个在java中反转LinkedList的算法不适合θ(N)？

Question

我的一个作业问题是编写一个算法来反转 LinkedList，在 θ(N) 时间内生成一个新列表。

我提出的代码不符合时间要求，我无法找出原因。

public Node reverse() {

    if (this == Node.NIL) {
        return Node.NIL;
    }

    if (this.getNext() == Node.NIL) {
        return new Node(this.getItem(), this.getNext());
    }

    Node curNode = new Node(this.getItem(), this.getNext());
    Node front = curNode;

    Node nextNode = null;
    Node prevNode = null;

    while (curNode.getNext() != Node.NIL) {
        nextNode = new Node(curNode.next.item, curNode.next.next);
        curNode.next = prevNode;
        prevNode = curNode;
        curNode = nextNode;
    }

    curNode.next = prevNode;
    front.setNext(Node.NIL);
    return curNode;
}

有一个名为 NIL 的节点，应称为 Node.NIL，它始终是提供的要反转的列表中创建的第一个节点，因此如果 Node.NIL 是下一个节点，您将位于列表的末尾.

每个节点都有 2 个属性，“next”和“item” - “next”是列表中的下一个节点，“item”是它携带的数据，在本例中是一个对象。

这是正在使用的测试 (NCASES = 20):

@Test
public void testReverseTiming() {
    int i;
    long diff = 0;
    for (i = 0; i < NCASES - 1; i++) {
        long start = System.nanoTime();
        Node result = nodes2[i].reverse();
        long end = System.nanoTime();
        diff = end - start;
        if (diff/1000000 > 250) {
            i++;
            break;
        }
    }
    long start = System.nanoTime();
    Node result = nodes2[i].reverse();
    long end = System.nanoTime();
    long diff2 = end - start;
    double ratio = (double) diff2 / (double) diff;
    assertTrue("reverse should scale linearly with list size", ratio > 1.2);
    assertTrue("reverse should scale linearly with list size", ratio < 2.5);
}

我的代码生成的比率范围为 25 到 35，而它需要介于 1.2 到 2.5 之间。

Answer 1

由于您的代码似乎只迭代列表一次，因此实际上似乎是 O(n)。

但是，您在外观中分配对象(new Node())，因此实际性能将取决于内存分配(其中包括对大型数据集的操作系统调用)和垃圾收集。两者都需要不确定的时间。这意味着即使算法(理论上)是 O(n)，测量的运行时间也将取决于 n 之外的其他因素。

您应该尝试重写算法来更改现有节点的链接，而不是创建新节点。 (我假设作业是反转现有列表，而不是创建列表的反转副本)