Реализация самого низкого общего предка - какая разница?

Question

Я читал о алгоритме самого низкого общего предка в верхнем кодере , и я не могу понять, почему задействован алгоритм RMQ - решение, перечисленное там, безумно сложно и имеет следующие свойства:

• O (sqrt (n)) сложность времени для поиска, O (n) сложность времени предварительного вычисления
• O (n) сложность пространства для хранения родителей каждого узла
• O (n) снова сложность пространства для хранения предварительных вычислений каждого узла

Мое решение: по 2 целочисленным значениям найти узлы с помощью простого обхода предварительного заказа.Возьмите один из узлов, поднимитесь по дереву и сохраните путь в наборе.Возьмите другой узел и поднимитесь по дереву и проверьте каждый узел по мере того, как я иду вверх: если узел находится в наборе, остановите и верните LCA. Полная реализация .

• O (n) временная сложность для нахождения каждого из 2 узлов, учитывая значения (потому что это обычное дерево, а не BST -
• O (log n) пространственная сложность для сохранения пути в Set
• O (log n) временная сложность для перехода по дереву со вторым узлом

Итак, учитывая этиЕсть два варианта, лучше ли алгоритм в Top Coder, и если да, то почему? Это то, что я не могу понять. Я думал, что O (log n) лучше, чем O (sqrt (n)).

public class LCA {

    private class Node {

        int data;
        Node[] children = new Node[0];
        Node parent;

        public Node() {
        }

        public Node(int v) {
            data = v;
        }

        @Override
        public boolean equals(Object other) {
            if (this.data == ((Node) other).data) {
                return true;
            }
            return false;
        }
    }
    private Node root;

    public LCA() {
        root = new Node(3);

        root.children = new Node[4];
        root.children[0] = new Node(15);
        root.children[0].parent = root;
        root.children[1] = new Node(40);
        root.children[1].parent = root;
        root.children[2] = new Node(100);
        root.children[2].parent = root;
        root.children[3] = new Node(10);
        root.children[3].parent = root;

        root.children[0].children = new Node[3];
        root.children[0].children[0] = new Node(22);
        root.children[0].children[0].parent = root.children[0];
        root.children[0].children[1] = new Node(11);
        root.children[0].children[1].parent = root.children[0];
        root.children[0].children[2] = new Node(99);
        root.children[0].children[2].parent = root.children[0];

        root.children[2].children = new Node[2];
        root.children[2].children[0] = new Node(120);
        root.children[2].children[0].parent = root.children[2];
        root.children[2].children[1] = new Node(33);
        root.children[2].children[1].parent = root.children[2];

        root.children[3].children = new Node[4];
        root.children[3].children[0] = new Node(51);
        root.children[3].children[0].parent = root.children[3];
        root.children[3].children[1] = new Node(52);
        root.children[3].children[1].parent = root.children[3];
        root.children[3].children[2] = new Node(53);
        root.children[3].children[2].parent = root.children[3];
        root.children[3].children[3] = new Node(54);
        root.children[3].children[3].parent = root.children[3];

        root.children[3].children[0].children = new Node[2];
        root.children[3].children[0].children[0] = new Node(25);
        root.children[3].children[0].children[0].parent = root.children[3].children[0];
        root.children[3].children[0].children[1] = new Node(26);
        root.children[3].children[0].children[1].parent = root.children[3].children[0];

        root.children[3].children[3].children = new Node[1];
        root.children[3].children[3].children[0] = new Node(27);
        root.children[3].children[3].children[0].parent = root.children[3].children[3];
    }

    private Node findNode(Node root, int value) {
        if (root == null) {
            return null;
        }
        if (root.data == value) {
            return root;
        }
        for (int i = 0; i < root.children.length; i++) {
            Node found = findNode(root.children[i], value);
            if (found != null) {
                return found;
            }
        }
        return null;
    }

    public void LCA(int node1, int node2) {
        Node n1 = findNode(root, node1);
        Node n2 = findNode(root, node2);
        Set<Node> ancestors = new HashSet<Node>();
        while (n1 != null) {
            ancestors.add(n1);
            n1 = n1.parent;
        }
        while (n2 != null) {
            if (ancestors.contains(n2)) {
                System.out.println("Found common ancestor between " + node1 + " and " + node2 + ": node " + n2.data);
                return;
            }
            n2 = n2.parent;
        }
    }

    public static void main(String[] args) {
        LCA tree = new LCA();
        tree.LCA(33, 27);
    }
}

Answer 1

Алгоритм LCA работает для любого дерева (не обязательно двоичного и не обязательно сбалансированного). Ваш анализ «простого алгоритма» не работает, так как отслеживание пути к корневому узлу - это фактически O (N) время и пространство вместо O (log N)

Answer 2

Просто хочу отметить, что проблема в корневом дереве, а не в бинарном дереве поиска. Итак, в вас алгоритм

O (n) временная сложность для нахождения каждого из 2 узлов, учитывая значения O (n) Пространственная сложность для хранения пути в Набор O (sqrt (n)) временная сложность для перехода вверх по дереву со вторым узлом и поиска в первых n-хранимых элементах.

Проверка каждого узла при переходе от второго узла с помощью take O (n), поэтому для n узлов потребуется O (sqrt (n)).

Answer 3

Алгоритм Harel и Tarjan LCA (ссылка в приведенной вами ссылке) использует предварительный расчет со сложностью O (n), после чего поиск составляет O (1) (не O (sqrt (n), как вы утверждаете).