Задача состоит в том, чтобы найти временную сложность в наихудшем случае m операций в структуре Union-Find структур "find" и "union", когда все операции "union" происходят перед всеми операциями "find".
Структура union-find начинается с n несвязанных наборов, каждый из которых содержит один элемент. Более того, каждый набор представлен в виде дерева, а структура использует сжатие путей и объединение по рангу.
Я думал о том, что прежде всего все операции объединения будут принимать O (log (n)), потому что каждая из них принимает O (1), и таких операций может быть не более log (n). .
После этого, если мы посмотрим на элементы поиска, то для каждого элемента первое обнаружение займет O (log (n)), но затем в следующий раз потребуется O (1) для каждого элемента на его пути. Поэтому потребуется меньше, чем O (m * log (n)).
Я не уверен, как именно продолжить. Я думал, что это может занять:
log (n) + log (n / 2) + log (n / 4) + .... = log (n) * log (n)
потому что каждый раз, когда уровень пути, по которому мы должны идти, становится короче.
Тем не менее. Я не уверен, а также не вижу, где здесь используется параметр m.
Возможно, в анализе также необходимо использовать обратную функцию Аккермана, но я не понимаю, как это сделать.