9Live Buchstaben Salat-Spiel

[negaH]

Das ist schon richtig, bezieht sich aber NICHT auf die Komplexität eines Algorithmus ansich.

Das mein DAWG Algo. langsammer als eine Scriptsprache wie PHP sein soll die dann sogar noch einen Algo benutzt der von seiner Komplexität wesentlich schlechter sein muß, halte ich für ein Gerücht. Sorry das ich das so deutlich sagen muß, das hat nichts mit einem persönlichen Angriff zu tuen.

Du sagst das du mit einem sortierten Array arbeitest. Gut, denn die Suchkomplexität in einem solchen Array ist O(ln n). Das ist defakto die gleiche Komplexität wie in einem Baum auf eine Node bezogen. Mit dem Unterschied das das Array[] als solches ja linear alle Einträge enthält der Baum aber linear alle Einträge zu einem Buchstaben. Somit ist die Gesamtkomplexität eines Suchbaumes abhängig von dem Alphabeth mit 256 Elementen mindestens 256 mal schneller als ein solches Array ! Das ist aber der Worstcase, denn in einer Wortliste werden ja nur 26+10 Buchstaben des Alphabeths tatsächlich benutzt. Wenn also bei einer Patternsuche oder kombinatorischen Suche in einem solchen Baum die Entscheidung für einen gefundenen Buchstaben gefallen ist so heist dies das alle nachfolgenden Kombinationen von vornherein 255/256'tel==99.6% aller Wörter ausgeschließen. Bei einem simplen sortierten Array ist dies nicht zwangsläufig der Fall.

Nun das DAWG ist ein solcher Suchbaum, aber mit der besonderen Eigenschaft der zusätzlich hohen Komprimierung im Vergleich zu einem Array[].

Wie gesagt ich kann es mir nicht vorstellen das eine Scriptsprache wie PHP mit einem schlechteren Algorithmus schneller sein sollte als eine nativ kompilierte Anwendung die einen mathematisch besseren Algo verwendet.

Sollte das tatsächlich der Fall sein so gibt es ein gewaltig großes Beben in meinem Glauben

Gruß Hagen