Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufgabe)

[marabu]

Guten Morgen.

Zitat von stoxx:

ab hier fängt die Zählung an für f

Erst durch diese Erklärung fällt mir auf, dass sich bei meiner Implementierung angrenzende Bereiche überlappen. Ich muss noch eine kleine Änderung an der abschließenden Berechnungsschleife einführen:

Delphi-Quellcode:

// ...
  // calculate result
  for i := High(seq) downto 0 do
  begin
    maxRange := rng[i];
    maxSymbol := seq[i];
    for j := i + maxRange to High(seq) do
      if (j = i) or (rng[j] > maxRange) then
      begin
        maxSymbol := seq[j];
        maxRange := rng[j];
      end;
    Result[Succ(i)] := maxSymbol;
  end;
// ...

Die als falsch eingestuften "Häufigkeitszählungen" in meinem Programm sind übrigens gerade der Schlüssel zur Umstellung der Laufzeitkomplexität auf O(n).

Schönes Wochenende

marabu