0

でこの実装を書き終えたところLinkedListです。私はこれが初心者の実装であることを知っています。確かにミスは多いです。insert(K key, V value)メソッドの最悪の場合のコストを誰かが教えてくれるかどうか知りたいだけです。O(n) にとどまるべきですか?

addLast()と のgetLast()メソッドで編集され、の代わりにLinkedList使用されます。ListIteratorIterator

public class 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

最悪の場合のコストは線形であり、リストの最後の要素の前に挿入する必要があるため、 -1 のエントリの量によって決まります。つまり、O(n) です。

于 2012-09-17T15:50:20.370 に答える
0

はい、O(n)です。

ただし、とforも同様でnあるため、 の定数乗数は最適ではありません が、それらを演算 - 、およびに置き換えることができます。つまり、新しいエントリの場所を見つけるための手順と、実際に挿入するための手順が必要になりましたが、実装を変更して で場所を見つけて挿入することができます。get(int)add(int, T)LinkedListO(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 に答える