Сохраняет ли это дополнение пространственно-временную сложность для DFS?

Question

Поэтому я реализовал стандартный поиск в глубину для дерева узлов, где каждый узел инкапсулирует состояние проблемы, которую я решаю, и я также добавил метод ниже, чтобы убедиться, что я не собираюсь повторять движение, расширяя узел, который инкапсулирует состояние, которое я уже проверил в каком-то предыдущем узле. Мой вопрос: этот метод каким-то образом изменяет временную или пространственную сложность алгоритма или они все еще являются типичными для DFS O(b^m) и O(bm) соответственно (где здесь b - коэффициент ветвления и m - максимальная глубина).

    //additional method which prevents us from repeating moves
    public boolean checkForRepeatedMoves(Node node) {
        Node nodeBeingChecked = node;

        //if the current node's state is the same as the state of its parent or its parent's parent and so on.. then we are repeating a move
        while (node.getParent() != null) {
            if(node.getParent().getState().isEqualTo(nodeBeingChecked.getState())) {
                return true;
            }
            node = node.getParent();
        }
        //if we have reached the root and no repetition is detected - return false
        return false;
    }

Answer 1

Пространство сложности

checkForRepeatedMoves похоже, не генерирует новое выделение объектов или не накапливает вызовы в стеке, поэтому он должен оставить общую пространственную сложность DFS неизменной.

Сложность времени

Давайте предположим checkForRepeatedMoves вызывается для каждого узла дерева и что дерево полностью заполнено на каждом уровне (условно говоря).

Давай позвоним c единица работы для проверки состояния сравниваемого узла с родительским узлом. Давайте предположим c постоянно.

Давайте разберем стоимость на каждом уровне дерева, от 1 (корень) до m,

• уровень 1: 0 (0 родитель посетил для 1 узла)
• уровень 2: b.c (1 родитель посетил для b корень детей)
• уровень 3: 2.b^2.c (2 родителя посетили b^2 узлы)
• ...
• уровень m + 1: m.b^m.c (м родители посетили для b^m узлы)

Итоговая стоимость C(m) можно записать как C(m) = c.S(m) где S(m) это сумма:

[1]: S(m) = 0 + b + 2.b^2 + ... + m.b^m

Давайте найдем асимптотический эквивалент S(m), Во-первых, давайте посмотрим, что

[2]: b.S(m) = 0 + b^2 + 2.b^3 + ... + m.b^(m+1)

Вычитание (1) из (2) дает:

[3]: (b - 1).S(m) = 0 - b - b^2 - b^3 - ... - b^m + m.b^(m+1)

Где мы можем определить геометрическую сумму b + b^2 + ... + b^m, что упрощает до [4]: (b^(m+1) - 1) / (b - 1) - 1,

Подставляя геометрическую сумму в правый размер равенства [3] на [4], а затем группируя члены по убыванию асимптотического доминирования, получаем

(b - 1).S(m) = m.b^(m+1) + p.b^m + q где p а также q постоянны по отношению к m,

когда m -> +Inf, у нас есть (b - 1).S(m) ~ (эквивалентно) m.b^(m+1),

Следовательно S(m) ~ [m/(b - 1)].b^(m+1) ~ m.b^m

Следовательно, стоимость эквивалентна C(m) ~ c.m.b^m

Так C(m) = O(m.b^m),

поскольку m.b^m "доминирует" b^m когда m -> +Inf, общая сложность вашего алгоритма становится O(m.b^m), от O(b^m) для обычного DFS. Следовательно, временная сложность увеличивается.