0

刚刚用LinkedList. 我知道这是一个初学者的实现。肯定有很多错误。我只想知道是否有人可以告诉我该insert(K key, V value)方法最坏情况的成本。我应该留在 O(n) 吗？

addLast()使用和中的getLast()方法进行编辑，LinkedList并使用ListIterator而不是Iterator.

公共类 SortedListPriorityQueue 实现 PriorityQueue {

protected List<Entry<K,V>> entries;
protected Comparator<K> c;

private static class MyEntry<K,V> implements Entry<K,V>{

    protected K key;
    protected V value;

    public MyEntry(K key, V value){
        this.key = key;
        this.value = value;
    }

    @Override
    public K getKey() {
        return this.key;
    }

    @Override
    public V getValue() {
        return this.value;
    }
}


/**
 * Crea la coda con il comparatore DefaultComparator
 */
public SortedListPriorityQueue() {
    entries = new LinkedList<Entry<K,V>>();
    c = new DefaultComparator<K>();
}

/* Utilizza un comparatore specifico
 public SortedListPriorityQueue(Comparator<K> comp) {}
*/

@Override
public int size() {
    return entries.size();
}

@Override
public boolean isEmpty() {
    return entries.isEmpty();
}

@Override
public Entry<K, V> min() {
    if(entries.isEmpty()) throw new RuntimeException("Priority queue is empty");
    else return entries.get(0);
}

@Override
public Entry<K, V> removeMin() {
    if(entries.isEmpty()) throw new RuntimeException("Priority queue is empty");
    else return entries.remove(0);

}

@Override
public Entry<K, V> insert(K key, V value) {
    Entry<K,V> new_entry = new MyEntry<K,V>(key, value);

    insertEntry(new_entry);
    return new_entry;
}

private void insertEntry(Entry<K, V> e) {
    //caso base1: lista vuota
    if(entries.isEmpty()){
        entries.add(e);
        return;
    }

    // caso base2: inserisce alla fine della lista
    else if(c.compare(e.getKey(), ((LinkedList<Entry<K, V>>) entries).getLast().getKey()) > 0){
        ((LinkedList<Entry<K,V>>) entries).addLast(e);
        return;
    }

    ListIterator<Entry<K,V>> it = entries.listIterator();
    Entry<K,V> current = null;

    while(it.hasNext()){
        current = it.next();
        if(c.compare(e.getKey(), current.getKey()) < 0){
            it.add(e);
            return;
        }
    }
}

}

4

4 回答 4

2

是的，您最坏的插入时间是O(n)- 插入出现在列表末尾附近的内容。您花O(n)时间找到正确的索引，然后花O(n)时间在里面LinkedList.add插入它。

于 2012-09-17T15:49:19.833 回答
1

优先队列可以通过使用堆实现的 O(log n) 插入来实现

于 2012-09-17T15:50:04.677 回答
0

是的，它是O(n)。

但请注意，常数的乘数n不是最优的，因为 get(int)和add(int, T)forLinkedList也是O(n)如此，但您可以将它们替换为O(1)操作-getLast()和。也就是说，现在它需要一些步骤来找到一个新条目的位置并实际插入它，但是您可以修改您的实现以找到一个位置并插入.addLast()ListIterator.add()O(n)O(n)O(n)O(1)

这样的替换不会改变算法的渐近复杂度（它仍然是O(n)），但会提高算法的典型实际性能。

O(ln n)当然，对于实际使用，最好使用提供插入和删除的基于堆的实现（例如内置实现） 。

于 2012-09-17T15:57:21.450 回答
0

最坏情况的成本是线性的，它取决于您拥有的条目数量 -1 ，因为这是您必须在列表中的最后一个元素之前插入的时候。所以它是O（n）。

于 2012-09-17T15:50:20.370 回答