доказательство временной сложности поиска объединения со сжатием пути

Question

Страница Википедии: Страница Википедии гласит, что

Если к n элементам применено m операций, либо Union, либо Find, общее время выполнения O (m log * n).

Подробный анализ этого результата:

Мои вопросы:

1. Разве сумма не должна быть (m+n)log*n вместо mlog*n?
2. Является ли средняя сложность времени для 1000 операций поиска такой же, как сложность времени каждого отдельного поиска?

Answer 1

Отказ от ответственности: Я все еще пытаюсь понять эти доказательства самостоятельно, поэтому не претендуйте на звание эксперта! Я думаю, что у меня может быть некоторое понимание, хотя.

1) Я думаю, что они предположили, что m = O (n), тем самым превращая O ((m + n) lg * (n)) в O (mlg *) (п)). В оригинальном доказательстве Тарьяна (о границе обратной функции Аккермана) (найденной здесь: https://dl.acm.org/doi/pdf/10.1145/321879.321884?download=true) он предполагает, что число m операций FIND превышает n. Во введении к алгоритмам (CLRS - гл.21) доказываемая ими граница предназначена для m операций, из которых n MAKE-SET. Кажется, что люди предполагают, что m будет асимптотически больше или равно n.

2) То, что они доказали, является амортизированной стоимостью для каждой операции. Это метод анализа, который ограничивает постоянным фактором время, затрачиваемое на серию операций, из которого можно тривиально вычислить среднее время за операцию. Есть несколько различных способов go об этом (я полагаю, что это пример агрегированного анализа?). Это стоит посмотреть!