algorithm - 递归函数的运行时

我试图找到此函数的运行时：

myst_fun_1([]) -> 0;
myst_fun_1(ListUsed = [_ | Tail]) -> length(ListUsed) + myst_fun_1(Tail).

因为这个长度函数是O(N)并且myst_fun_1被称为N次，运行时会是O(N^2)吗？我想知道我的理解是否正确。

最佳答案

myst_fun_1([]) -> 0;

myst_fun_1(ListUsed) ->
    myst_fun_1(length(ListUsed), ListUsed).

myst_fun_1(Length, [_ | Tail]) ->
    Length + myst_fun_1(Length-1, Tail).

O（N）

关于algorithm - 递归函数的运行时，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52287897/