插入未排序的链表不应该只是 O(n) 而不是 O(1) 或 O(n) 吗？

Question

这属于来自 Whosebug 的 "a software algorithm"。com/help/on-topic，在本例中，是一种将项目添加到未排序数组列表的软件算法。

这是我们在class中制作的关于不同数据结构的运行次操作的图表

我想重点关注的是将一个值插入到未排序的数组列表中。这是我们这样做的代码

 public void insert(E value) {
    insertAtIndex(size, value);
}
public void insertAtIndex(int index, E value) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("index: " + index);
    }
    if (size == 0) {
        ListNode<E> newNode = new ListNode<E>(value);
        front = back = newNode;
    }
    else {

        if (index == 0) {
            ListNode<E> newNode = new ListNode<E>(value, front);
            front = newNode;
        }
        else {
            ListNode<E> current = nodeAt(index - 1);
            ListNode<E> newNode = new ListNode<E>(value, current.next);
            current.next = newNode;
            if (index == size) {
                back = newNode;
            }
        }       

    }
    size++;
}
 private ListNode<E> nodeAt(int index) {
    ListNode<E> current = front;
    for (int i = 1; i <= index; i++) {
            current = current.next;
    }
    return current;
}

你对insert方法做运行时间分析，不就是O(n)，不是O(1)或O(n)吗？我知道插入方法如何在 O(1) 中运行。如果 size == 0，您只需执行一两个快速操作，创建新节点并将其分配给前面。

然而，根据运行时间分析，https://academics.tjhsst.edu/compsci/CS2C/U2/bigoh.html，当你评估if else if branch of insert at index时，你不应该"assume the worst case and and thus the running time of the if/else will be the sum of the running time of the test and the running time of the worst-case statement"。如果你这样做，你会看到最坏的情况运行时间在 else 分支中，因为它涉及 nodeAt 方法，它在 O(n) 中运行s。

因此，整个 insertAtIndex 和插入方法运行的复杂度不是 O(n)，不是 O(1) 吗？从我在图表中看到的，O(1) 将被解释为正确的可能性。但是从那个分析来看，O(n)应该是唯一的可能了。

Answer 1

是的，您的插入代码运行s 复杂度为 O(n)。对于 O(1) 中的运行，它应该在索引 0 处插入，而不是在列表的末尾插入。

一般来说，可以在 O(f) 中完成某些事情的声明并不是说每个实现都是 O(f)，而是说最佳实现是 O(f)。

您的第二个困惑是关于 table 中的条目 "O(1) or O(n)"。它们对应于未排序（因此插入可以在索引 0 处插入）或已排序（因此插入必须找到正确的插入点）的链表。

插入未排序的链表不应该只是 O(n) 而不是 O(1) 或 O(n) 吗？

Shouldn't insert just be O(n) not O(1) or O(n) inserting into unsorted linked list?

java

algorithm

for-loop

linked-list

runtime