不应插入O（n）而不是O（1）或O（n）插入未排序的链表中？

这来自stackoverflow.com/help/on-topic的“软件算法”，在这种情况下，这是一种将项目添加到未排序数组列表的软件算法。不应插入O（n）而不是O（1）或O（n）插入未排序的链表中？

这是图表，我们在类在关于操作对不同的数据结构 enter image description here

一个我想关注的是插入一个值转换成排序的数组列表中的运行时。这是我们这样做的

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; 
}

当你插入方法做运行时分析代码，是不是只是为O（n），而不是O（1）或O（N）？我得到了如何在O（1）中运行插入方法。如果大小== 0，则只需执行一个快速操作，创建新节点并将其分配给前端。

然而，在运行时分析方面，https://academics.tjhsst.edu/compsci/CS2C/U2/bigoh.html，当您评估是否在索引处插入分支时，您是否应该“假设最坏的情况并且因此if/else的运行时间将是总和测试运行时间和最坏情况声明的运行时间“。如果你这样做，你会发现最差情况下的运行时间在else分支中，因为它涉及在O（n）中运行的nodeAt方法。

因为这样会不会在O（n）中运行整个insertAtIndex和insert方法，而不是O（1）？从我在图表中看出，O（1）将被解释为一种正确的可能性。但从这个分析来看，O（n）应该是唯一的可能性。

来源

2015-02-07 committedandroider

其实如果你想这样说，那么nodeAt（2）是O（2）.. nodeAt（3）是O（3）..等等。你在想太多。作为程序员，我们尽量避免思考。 – Qwertyzw 2015-02-07 01:58:05

您可以保留一个指向列表最后一个元素的指针。这样可以避免您对'nodeAt（index - 1）'的调用，并立即在最后插入新元素。 – homeless 2015-02-07 01:58:48

@homeless该实现没有右侧的列2的后向指针。 – committedandroider 2015-02-07 02:00:14

是的，你的插入代码在O（n）中运行。要在O（1）中运行，它应该在索引0处插入，而不是在列表的末尾。通常，在O（f）中可以做的事情的陈述不是每个实现都是O（f）而是最优实现是O（f）的陈述。

您所遇到的第二个困惑是关于表中的条目“O（1）或O（n）”。它们对应于未排序的链接列表（因此插入可以在索引0处插入）或排序（因此插入必须找到正确的插入点）。

来源

2015-02-07 02:18:44

是啊我是如何错过未排序的vs排序的部分......所以关注细节，但错过了大局 – committedandroider 2015-02-07 02:23:34

不应插入O（n）而不是O（1）或O（n）插入未排序的链表中？

回答

相关问题