Programmiertechnik max finden zwei arrays

[Rolf b]

Zum Rechenaufwand: Die Kreuzkorrelation skaliert mit dem Quadrat der Anzahl n der Messwerte. Der Rechenaufwand beim Sortieren skaliert zwischen Quadrat und n mal log(n), also etwas günstiger.

Wieso? Für ein $$\tau$$ hast Du genau eine Schleife, ohne Schachtelung. Ich würde sagen, dass EIN Korrelationswert in $$O(n)$$ berechenbar ist. $$O(n^2)$$ hast Du, wenn Du die Korrelationen für alle möglichen Verschiebungen bestimmen willst (unter Vernachlässigung des Umstandes, dass wegen endlich langer Arrays die Laufzeit für eine Korrelationsberechnung um so kürzer wird, je größer das Delta ist) - deshalb ja auch mein Vorschlag mit der $span-Halbierung, dann kommst Du wieder bei $$O(n \cdot \log n)$$ heraus.

Rolf