Was ist die Big-O stack, queue, set und deque?

Das hängt wirklich von der Umsetzung der einzelnen Daten-Struktur. Ich gehe über ein paar, so dass Sie können erhalten eine Idee davon, wie diese zu ermitteln.

Angenommen, der Stack-Klasse implementiert ist, mit einem Node (es kann umgesetzt werden mit einem LinkedList, ArrayList, arrray usw. als gut).

Node top, bottom;
public Stack(Node n){
    top = bottom = n;
}

Stack hat 3 primären Methoden: peek, push, und pop.

public int peek(){
    return top.value; //only return value
}

Gab es nicht viel Verarbeitung beteiligt. Es kam gerade ein primitiver Wert. Dies ist O(1) für Zeit und Raum.

public void push(Node n){
    n.next = top;
    top = n;
}

Immer noch keine wirkliche Verarbeitung. Dies ist O(1) für Zeit und Raum. Lassen Sie uns überspringen pop() und versuchen, etwas mehr interessant. Lassen Sie uns versuchen, eine Methode genannt contains(int v). Es durchsucht den Stapel, um zu sehen, ob es enthält eine Node enthält einen Wert, der gleich zu v.

public bool contains(int v){
    Node current = top;
    while(current != null){
        if(current.value == v){
            return true;
        }
        current = current.next;
    }
    return false;
}

Grundsätzlich fahren wir durch den Knoten Verweise, bis wir den Wert gefunden haben, oder wir das Ende erreichen. In einigen Fällen werden Sie feststellen, Wert früh und in einigen Fällen später die Straße hinunter. Jedoch, wir kümmern uns um den schlimmsten Fall! Der Schlimmste Fall wäre, müssen wir schauen jedes einzelne Node. Sagen, es gibt n Knoten, dann haben wir O(n).

Können Sie diese Analyse-Fähigkeiten, um die anderen Daten Strukturen, so dass Sie lösen können Sie den rest selbst. Es ist nicht allzu schlimm. Viel Glück. 🙂

InformationsquelleAutor But I'm Not A Wrapper Class

Das Problem hier ist, dass diese Datenstrukturen sind in der Regel umgesetzt in Bezug auf andere. Zum Beispiel, ein set umgesetzt werden könnten, als eine hash-Tabelle oder mit einem rot-schwarz-Baum-Algorithmus.

Einen Stapel nicht zufälligen Zugriff, aber oft implementiert als block Arbeitsspeicher (z.B. ein array mit einem einzelnen element zeigt auf der stack-Spitze, die aktualisiert wird, für push und pop Operationen.

Einen queue könnte implementiert werden als ein array oder einer verknüpften Liste mit sehr unterschiedlichen einfügen, entfernen und Indexierung Eigenschaften. Ein deque ist eher umgesetzt werden als eine verknüpfte Liste, aber die Microsoft-Implementierung in der C++ - standard-Bibliothek verwendet einen hybrid-Ansatz (siehe Was die heque ist Los mit den Speicher-overhead von std::deque?).

InformationsquelleAutor Steve

Big-O-notation ist in der Regel reserviert für algorithmen und Funktionen, Daten-Typen.

Darüber hinaus die Zeit, die Komplexität hängt sehr stark von der Umsetzung. Fragen, für die Big-O-Zeit-Komplexität von einem "stack" - Datentyp ist wie zu Fragen, für die Big-O-Zeit, die Komplexität der "Sortierung". Es hängt alles von der Umsetzung. (Genauer gesagt, eine bestimmte Fall-spezifische Optimierungen und Anforderungen können sich ändern, die Zeit-Komplexität erheblich zu.)

Wenn Sie schauen, um die C++ - STL als Referenz-Implementierung, Sie können finden die details auf die Komplexität der einzelnen aufgeführten Datentypen von hier aus. Suche einfach nach Datentyp und operation.

InformationsquelleAutor Mr. Llama