Erlang 扁平化函数时间复杂度

Question

我需要以下方面的帮助：

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

感谢您的帮助。

Answer 1

首先，我不确定您的代码能否正常工作，至少不能像标准库那样正常工作。您可以将您的函数与 lists:flatten/1 进行比较，并可能改进您的实现。尝试将 [a, [b, c]] 和 [[a], [b, [c]], [d]] 等列表作为输入并验证您 return 是否符合您的预期。

关于复杂性，由于 ++ 运算符和语言的功能（不可变）性质，它有点棘手。 Erlang 中的所有列表都是 linked 列表（不像 C++ 中的数组），你不能只在列表的末尾添加一些东西而不修改它；在它指向列表末尾之前，现在您希望它 link 指向其他内容。同样，由于它不是可变语言，您必须复制 ++ 运算符左侧的整个列表，这会增加该运算符的复杂性。

您可以说 A ++ B 的复杂度是 length(A)，这会使您的函数的复杂度稍微大一点。它会像 length(FirstElement) + (lenght(FirstElement) + length(SecondElement)) + .... 直到（没有）最后，经过一些数学魔法可以简化为 (n -1) * 1/2 * k * k 其中 n 是元素的数量，而 k 是平均值元素的长度。或者 O(n^3).

如果您是新手，它可能看起来有点奇怪，但通过一些练习您可以掌握它。我建议浏览一些资源：

良好的 explanation 列表及其创建方式
关于 list handling 的文档，包含 DO 和 DO NOT 部分
++ 个运算符神话和最佳实践的简短 description
Chapter 关于递归和尾递归以及使用 ++ 运算符的示例

Erlang 扁平化函数时间复杂度

Erlang flatten function time complexity

erlang

time-complexity

flatten