をフラット化：Erlangのは、私は次のヘルプを必要とする機能の時間複雑
flatten ([]) -> [];
flatten([H|T]) -> H ++ flatten(T).
入力リスト例えば、異なる長さ
と他のリストが含まれています。
flatten([[1,2,3],[4,7],[9,9,9,9,9,9]]).
時間複雑である何この関数の？ なぜですか？
私はO（n）に達しました。ここで、nは入力リストの要素の数です。例えば
：助けを
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
感謝。
まず、あなたのコードが動作するかどうかはわかりません。少なくとも、標準ライブラリの仕組みはそうではありません。あなたはlists:flatten/1とあなたの機能を比較して、あなたの実装を改善することができます。 [a, [b, c]]と[[a], [b, [c]], [d]]などのリストを入力し、期待どおりの結果を返すかどうかを確認してください。
複雑さに関しては、++という演算子と機能的な（変更不能な）性質のために少し難解です。 Erlangのすべてのリストはリンクリスト（C++のような配列ではありません）であり、変更せずに最後に何かを追加することはできません。リストの終わりを指す前に、今は別のものにリンクしたいと思っています。そしてまた、それは変更可能な言語ではないので、++演算子の左にあるリスト全体をコピーしなければならず、この演算子の複雑さが増します。
A ++ Bという複雑さはlength(A)であり、関数の複雑さが少し高くなると言えます。 length(FirstElement) + (lenght(FirstElement) + length(SecondElement)) + ....のようになります。最後には、いくつかの数学的マジックを(n -1) * 1/2 * k * kに簡約することができます。nは要素の数であり、kは要素の平均の長さです。またはO(n^3)。
これは少し奇妙に思えるかもしれませんが、いくつかの練習では、それを取得することができます。私はいくつかのリソースを経由推薦する：DO
++オペレータの神話と最高のNOTパーツ実践++オペレータ