这段（简单）代码的时间复杂度是多少？

Question

我试图弄清楚以下代码的运行时间，无论列表是ArrayList还是LinkedList。感谢您的任何建议！ Array: 我认为删除操作的时间复杂度是O(n)，循环的时间复杂度是N/2，所以总时间复杂度是O(n^2)。

LinkedList: 只有引用会改变，所以删除操作的时间复杂度是常数级别，循环的时间复杂度是N/2，所以总时间复杂度是O(n)。

int halfSize = lst.size() / 2;

for (int i = 0; i < halfSize; i++){
    lst.remove(0);
}

- user2827214

---

这里勉强可以接受，我认为不必因此而发起关闭投票。尽管问题很简单，但它包含了基本的尝试。 - nanofarad

看来你的判断是准确的：ArrayList.remove(0) 的时间复杂度为O(n)，如果运行n / 2次，则为O(n^2)。而LinkedList.remove(0)的时间复杂度为O(1)，因此这将是O(n)。 - Leo Izen

@ColeJohnson 关于复杂度的问题不一定是离题的；你为什么认为我们有这个标签呢？ - arshajii

@ColeJohnson Programmers.se 关注软件设计和开发的概念。这是一个具有具体代码的特定问题。它非常适合在 SO 上提问。 - arshajii

@arshajii 好的，没问题。 - Cole Tobin

Answer 1

ArrayList： 由于底层的数组复制，评估正确。

    public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // Let gc do its work

    return oldValue;
}

链表： 评估正确，零索引处的节点删除是常数时间。

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

- Origineil

---

我们正在从链表的头部进行删除，这是一个O(1)的操作。 - arshajii

真的...忘记了索引始终为0。已做出修改。 - Origineil

考虑到这一点，我认为作者的评估没有问题。 - Origineil