Ich lese ein Buch mit dem Titel Principles of Computer Science (2008) von Carl Reynolds und Paul Tymann (herausgegeben von Schaum's Outlines).
Das zweite Kapitel enthält eine Einführung in Algorithmen mit einem Beispiel für eine sequentielle Suche, die einfach eine Liste von Namen durchläuft und WAHR zurückgibt, wenn ein bestimmter Name in der Liste gefunden wird.
Der Autor fährt fort (Seite 17):
Wir sagen, dass die "Wachstumsordnung" des sequentiellen Suchalgorithmus n ist. Die Notation dafür ist T (n). Wir sagen auch, dass ein Algorithmus, dessen Wachstumsordnung innerhalb eines konstanten Faktors von T (n) liegt, ein Theta von NL say hat. "Die sequentielle Suche hat ein Theta von n." Die Größe des Problems ist n, die Länge der durchsuchten Liste.
Ich finde es wirklich schwer zu folgen. Das Buch ist mit Fehlern durchsetzt, daher bin ich mir nicht sicher, ob ich etwas vermisse oder ob es einen Tippfehler im obigen Absatz gibt. Im allgemeinen Englisch sehe ich selten, dass ein Satz mit "... say" endet.
Ich bin sehr verwirrt.
Wofür steht T? Das Buch erklärt nicht. Ist es für die Zeit oder für Theta?
Wenn "ein Theta von NL" bedeutet "Die sequentielle Suche hat ein Theta von n." Wofür steht L? 'Linear' oder 'Länge'?
Ich habe an die Verlage geschrieben und um eine Erklärung gebeten. Sie sagten, sie würden meine Nachricht an die Autoren weiterleiten. Sie haben nicht geantwortet. Ich habe auch versucht, nach anderen Quellen zu suchen, aber ich habe immer noch das nörgelnde Gefühl, dass ich etwas missverstehe - kann mich also nicht ausruhen, bis ich diesen Absatz entschlüsselt habe.
Wenn jemand eine Kopie dieses Buches hat und diesen Absatz verstanden hat. Dann würde ich mich freuen, wenn Sie mir mitteilen könnten, ob dieser Absatz korrekt ist, oder ihn mit anderen Worten erklären. Vielen Dank.
Antworten:
Der Absatz ist falsch. Leider sieht es genau so aus, als würde ein Schüler, der das Material nicht versteht, als Antwort auf eine Übung schreiben. Diese Art von Unsinn hat keinen Platz in einem Lehrbuch. Mach keine plötzlichen Bewegungen. Leg das Buch weg. Treten Sie von dem Buch zurück.
No. ist die Bezeichnung für eine Funktion , genannt , die ein Argument namens nimmt . Mit dieser Funktion kann alles Mögliche gemeint sein. Es gibt eine gewisse Tradition, Wiederholungsrelationen für die Laufzeit von Programmen in der Form zu schreiben, z. B. Aber ist hier keine "Wachstumsordnung": Es ist eine spezifische Funktion, die durch eine Wiederholungsrelation definiert wird. Und Sie können nicht einfach " " schreiben und erwarten, dass die Leute Ihre Gedanken lesen und wissen, dass die Funktion die Laufzeit eines Algorithmus angibt. hier steht für Zeit.T(n) T n
Dies wurde offensichtlich entstellt. Ich denke, die Autoren wollten etwas schreiben wie:
Aber bitte, wir sagen nicht "hat ein Theta von ", so wie, wenn Ihre Notation für Höhe ist, Sie nicht sagen würden "John hat ein von 180 cm". Es ist einfach keine richtige Form von Wörtern. Wir sagen tatsächlich: "Die Laufzeit des Algorithmus ist Theta (oder Theta von )." Beachten Sie insbesondere, dass ein Werkzeug ist, um über mathematische Funktionen zu sprechen, nicht über Algorithmen. Theta bedeutet nicht, dass die Laufzeit etwas ist; Vielmehr können Sie damit über die Laufzeit sprechen.n h h n n Θ
"NL" bezeichnet im Übrigen den nichtdeterministischen Lograum der Komplexitätsklasse , der an der Stelle, an der er im ursprünglichen Zitat erschien, überhaupt keinen Sinn ergibt .
quelle
Es hört sich so an, als würde der Autor versuchen, die Big O- Notation zu erklären , hat sie jedoch ohne besonderen Grund in umbenannt und den Text vollständig entstellt.T
Für eine gute Beschreibung der Big O- Notation (sowie von little-o und Theta) empfehle ich das MIT-Buch Introduction to Algorithms von Prof. Leiserson.
Es scheint, dass ein wichtiger Unterschied darin besteht, dass sich die auf die Gesamtkomplexität eines Algorithmus bezieht, bei dem es sich typischerweise um Zeit , Raum oder beides handelt. (zB Einige Algorithmen laufen langsamer mit größeren Datensätzen, einige benötigen mehr Speicherplatz mit größeren Daten, und einige benötigen sowohl mehr Zeit und mehr Platz) .O−notation
Es scheint , dass diese bezieht sich nur auf die Zeitmessung eines Algorithmus und berücksichtigt nicht die Speicheranforderungen.T−notation
quelle