Erlang abflachen Komplexität Funktion Zeit

Question

ich mit folgenden eine Hilfe benötigen:

flatten ([]) -> []; 

flatten([H|T]) -> H ++ flatten(T). 

Eingangsliste enthält weitere Listen mit unterschiedlicher Länge

Zum Beispiel:

flatten([[1,2,3],[4,7],[9,9,9,9,9,9]]). 

Was ist die Zeitkomplexität von dieser Funktion? Und warum?

Ich habe es zu O (n), wobei n eine Anzahl von Elementen in der Liste Eingabe ist.

Zum Beispiel:

flatten([[1,2,3],[4,7],[9,9,9,9,9,9]]) n=3 

flatten([[1,2,3],[4,7],[9,9,9,9,9,9],[3,2,4],[1,4,6]]) n=5 

Vielen Dank für Hilfe.

Answer 1

Zunächst bin ich mir nicht sicher, ob Ihr Code funktioniert, zumindest nicht so, wie die Standardbibliothek funktioniert. Sie könnten Ihre Funktion mit lists:flatten/1 vergleichen und vielleicht Ihre Implementierung verbessern. Versuchen Sie Listen wie [a, [b, c]] und [[a], [b, [c]], [d]] als Eingabe und überprüfen Sie, ob Sie zurückgeben, was Sie erwartet haben.

In Bezug auf Komplexität ist es wenig schwierig wegen ++ Operator und funktionale (unveränderliche) Natur der Sprache. Alle Listen in Erlang sind verkettete Listen (nicht Arrays wie in C++), und Sie können nicht einfach etwas zu Ende hinzufügen, ohne es zu modifizieren; Bevor es auf das Ende der Liste zeigt, möchten Sie es jetzt mit etwas anderem verknüpfen. Und wieder, da es keine veränderbare Sprache ist, müssen Sie eine Kopie der gesamten Liste links vom ++ Operator erstellen, was die Komplexität dieses Operators erhöht.

Sie könnten sagen, dass die Komplexität von A ++ Blength(A) ist, und es macht die Komplexität Ihrer Funktion ein wenig größer. Es würde so etwas wie length(FirstElement) + (lenght(FirstElement) + length(SecondElement)) + .... bis (ohne) zuletzt gehen, was nach einiger Mathe-Magie zu (n -1) * 1/2 * k * k vereinfacht werden könnte, wo n die Anzahl der Elemente ist, und k ist die durchschnittliche Länge des Elements. Oder O(n^3).

Wenn Sie neu sind, mag es etwas merkwürdig erscheinen, aber mit etwas Übung können Sie sich davon abhalten. Ich würde empfehlen, durch wenige Ressourcen gehen:

• Gut explanation von Listen und wie sie erstellt werden
• Dokumentation auf list handling mit DO und NICHT Teile
• Kurz description von ++ Betreiber Mythen und am besten Praktiken
• Chapter über Rekursion und Tail-Rekursion mit Beispielen mit ++ Operator