Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufgabe)

[marabu]

Hi stoxx,

dein erstes Beispiel hatte einen Fehler - du erinnerst dich? Die Beschreibung des Algorithmus ist nicht vollständig - der Begriff Häufigkeit ist nicht ausreichend definiert. Mir fehlen zuverlässige Testfälle zur Verifikation einer Implementierung. Als Referenz bietest du mir deinen Code an. Ich habe ihn analysiert und musste als erstes festgestellen, dass du jeweils den ersten Buchstaben eines Abschnittes nicht in die Häufigkeitszählung (CountArray) einfließen lässt. Interessanterweise hat das bei mehreren Testsequenzen keinen Einfluss auf das Ergebnis, aber es erschüttert auch mein Vertrauen in deinen Referenzcode.

Eines ist mir inzwischen klar - mein ursprüngliches Problemverständnis ist falsch, da ich die lückenhaften Informationen durch Fehlinterpretation geschlossen habe. Damit ist auch mein Code unbrauchbar, obwohl er gelegentlich richtige Eregbnisse gebracht hatte. Häufigkeiten waren in meinem Code homogene Teilkettenlängen. In deiner Implementierung interessieren keine statischen Häufigkeiten, weder die Häufigkeit in der Eingabesequenz, noch die Häufigkeit im untersuchten Abschnitt. Du arbeitest mit einer dynamischen Häufigkeit im Abschnitt. (Sequenz nenne ich hier die ursprüngliche Eingabe, Abschnitt die iterativ um eine Stelle gekürzte Sequenz.)

Ich hatte schon sehr früh auf die Bedeutung einer vollständigen und korrekten Beschreibung für den Algorithmus hingewiesen. Der von dir zitierte Text scheint nur ein Fragment deiner Aufgabenstellung zu sein. Aus Gründen die ich nur ahnen kann, scheust du die Preisgabe von Hintergrundinformationen.

Wenn die dynamische Berechnung der Häufigkeit in deinem Code korrekt ist, dann wirst du wohl prinzipiell von O(n*n) nicht wegkommen. Eine Voraussetzung für die Reduktion der Komplexität wäre eine feste Intervallgrenze (eine genügt), aber was ich hier mit dynamischer Berechnung bezeichne, basiert auf einem sliding window - da ist keine Vorberechnung der Häufigkeiten sinnvoll.

Freundliche Grüße vom marabu