Какова (большая O) сложность этого алгоритма? - PullRequest
Новая
       19

Какова (большая O) сложность этого алгоритма?

0 голосов
/ 12 ноября 2018

Код ищет количество возможных путей действий, которые достигают цели.Я не хочу его оптимизировать, просто знаю сложность 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) или другой вариант.

1 Ответ

0 голосов
/ 12 ноября 2018

Как уже отмечалось в некоторых комментариях, сложность времени равна O(n!).

Что касается использования памяти , actionSubset() создает новый список каждый раз, когда он вызывается (в отличие от того, чтобы алгоритм работал с оригиналом). Но поскольку все списки, кроме исходного, выпадают из области видимости в конце каждой итерации, использование памяти будет только увеличиваться на n как функция размера usableActions, поэтому n!.

...