Die Bestimmung der Zeit-und Raum-Komplexität

Ich bin mit einigen Schwierigkeiten Bestimmung der Raum-und Zeit-Komplexität. Zum Beispiel, wenn ich einen Baum mit einer Verzweigung Faktor b und haben bei den meisten eine Tiefe d, wie kann ich die Berechnung der Zeit-und Raum-Komplexität? Ich weiß, Sie sind in O(b^d) und O(bd) , aber mein problem ist, wie man auf diese Werte.

Dank!

  • Asymptotische Komplexitäten sind nicht Werte. Sie sind Formeln. Wenn Sie möchten, dass die genauen Werte sollten Sie sprechen von Zeit, Raum und Kosten. Dann die nächste Frage, zumindest für die Zeit Kosten, werden "Zeit zu tun, was?" Besuchen Sie jedes element in dem Baum? Finden Sie den Pfad von der Wurzel zu einem Blatt, auf dem die Knoten die kleinste Summe? Setzen Sie den Baum in eine Art Normalform? Nur Vorgänge, die Zeit Kosten und der Komplexität. Datenstrukturen nur da sitzen.
Schreibe einen Kommentar