Не следует вставлять только O (n) не O (1) или O (n) вставлять в несвязанный список?

Question

Это подпадает под «программный алгоритм» из stackoverflow.com/help/on-topic, в данном случае программный алгоритм для добавления элемента в список несортированных массивов.

Это графики мы сделали в классе о время работы операций на различных структуры данных

Один я хочу сосредоточиться на вставляю значение в несортированным список массива. Вот наш код для этого

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 (п), а не O (1) или O (п)? Я понимаю, как метод вставки может выполняться в O (1). Если size == 0, вы просто выполняете две быстрые операции, создаете новый узел и назначаете его на передний план.

Однако в отношении анализа времени выполнения, https://academics.tjhsst.edu/compsci/CS2C/U2/bigoh.html, когда вы оцениваете, если else, если ветвь вставки в индексе, вы не должны «принимать наихудший случай и, следовательно, время выполнения if/else будет суммой времени работы теста и времени работы наихудшего случая ». Если вы это сделаете, вы увидите, что худшее время выполнения в ветке else, потому что оно связано с методом nodeAt, который работает в O (n).

Из-за этого не будут работать все методы insertAtIndex и insert в O (n), а не O (1)? Из того, что я вижу на диаграмме, O (1) интерпретируется как правильная возможность. Но из этого анализа O (n) должна быть единственной возможностью.

Answer 1

Да, код вставки работает в O (n). Для запуска в O (1) он должен вставляться в индекс 0, а не в конец списка.

В общем случае утверждение о том, что что-то может быть сделано в O (f), не является утверждением, что каждая реализация O (f), а не оптимальная реализация - O (f).

Вторая путаница, которая у вас есть, касается записей «O (1) или O (n)» в таблице. Они соответствуют несопоставимому связанному списку (поэтому вставка может вставляться в индекс 0) или сортироваться (поэтому вставка должна найти правильную точку вставки).