这个算法的（大O）复杂度是多少？

Question

代码搜索达到目标的可能行动路径的数量。我不想优化它，只知道它具有的 Big-O 复杂性。代码如下：

private int countPaths(Node parent, List<Action> usableActions, Node goal)
{
    int counter = 0;
    foreach(Action act in usableActions)
    {
        Node node = generateNewNode(parent, act); // Only generate the new node O(1)
        if (node.isEquals(goal)) //Check goal
        {
            counter++;
        }
        else
        {
            List<Action> subset = actionSubset(usableActions, act); // return usableAction with act removed
            counter += countPaths(node, subset, goal); // usableActions - 1
        }
    }
    return counter;
}

第一个循环会给算法带来 O(n) 的复杂度，但是进行递归调用不知道它是 O(n^2)、O(n^n) 还是其他选项。

Answer 1

正如一些评论中所述，时间复杂度 是 $O(n!)$ 。

至于内存使用，actionSubset() 每次调用都会创建一个新列表（而不是让算法对原始列表进行操作）。但是因为除了原始列表之外的所有列表在每次迭代结束时都超出范围，内存使用量只会增长 $\frac{n(n+1)}{2}$ 作为 usableActions 大小的函数，所以 $O(n^2)$ .

这个算法的（大O）复杂度是多少？

What is the (big O) complexity of this algorithm?

algorithm

recursion

complexity-theory

big-o