Есть вопрос о назначении, которое должно было быть сделано сегодня, для которого были выпущены решения, и я не понимаю правильного ответа. В этом вопросе рассматривается производительность непересекающихся множеств в форме лесов непересекающихся множеств , в которых для повышения производительности используется алгоритм взвешенного объединения (корень меньшего дерева в качестве дочернего элемента связан с корнем большее из двух деревьев), но без с использованием алгоритма сжатия пути.
Вопрос в том, является ли наилучшая производительность выполнения (n-1) операций объединения на n одноэлементных узлах и m> = n операций поиска в любом порядке Omega (m * logn), которое, как подтверждает решение, является правильным, как это:
Существует последовательность S из n-1 Союзов, за которой следует m> = n Находит, что занимает Омега (m log n) время. Последовательность S начинается с последовательности n-1 союзов, которая строит дерево с глубиной омега (log n). Тогда он имеет m> = n Находит, каждый для самого глубокого листа этого дерева, поэтому каждый берет
(log n) время.
Мой вопрос таков: почему это доказывает, что нижняя граница Omega (m * logn) верна? Разве это не отдельный пример того, когда границей будет Omega (m * logn), которая не доказывает это для всех входов? Я уверен, что при опровержении заявки нужно показать только один контрпример, но нужно доказать предикат для всех возможных входных данных, чтобы доказать его правильность.
В своем ответе я указал на тот факт, что у вас может быть случай, когда вы начинаете, соединяя два одноэлементных узла вместе. Затем вы присоединяете другой синглтон к этому дереву с 2 узлами с 3 узлами, совместно использующими одного и того же родителя, затем другого и т. Д., Пока не объедините все n узлов. Затем у вас есть дерево, в котором все n-1 узлы указывают на одного и того же родителя, что по сути является результатом, который вы получите, если используете сжатие пути. Тогда каждый НАХОДКА выполняется за O (1) раз. Таким образом, последовательность (n-1) Союзов и m> = n Finds заканчивается тем, что Omega (n-1 + m) = Omega (n + m) = Omega (m).
Не означает ли это, что предел Omega (m * logn) не является жестким и, следовательно, утверждение неверно? Я начинаю задумываться, не понимаю ли я полностью Big-O / Omega / Theta: /
РЕДАКТИРОВАТЬ: исправил вопрос, чтобы быть немного яснее
EDIT2: Вот оригинальный вопрос , как он был представлен, и решение (мне потребовалось немного времени, чтобы понять, что Гамбарино и другой парень полностью выдуманы; хардкор итальянский проф)