Есть ли пример создания алгоритма Union & find без объединения по рангу в Omega (q log n)?

Да, существует соответствующая нижняя граница, созданная Майклом Дж. Фишером в 1972 году (см. раздел 3). В его примере используется биномиальное дерево глубины log n, где биномиальное дерево глубины 0 — это один узел, а биномиальное дерево глубины k — это два биномиальных дерева глубины k — 1, корень одного из которых указывает на корень другого. . Повторно беря объединение корней биномиального дерева, чтобы указать на один элемент, и выполняя поиск в самом глубоком узле, мы выполняем дорогостоящую (логарифмические шаги) операцию, которая оставляет для использования другое встроенное биномиальное дерево.

Демонстрация Python: это печатает (k+1) * 2**k, где k — аргумент example, представляющий приблизительное количество операций для O(2**k) операций с O(2**k) клавишами.

p = {}

def find(a):
    global count
    b = a
    while (b in p):
        count += 1
        b = p[b]
    while (a in p):
        pa = p[a]
        p[a] = b
        a = pa
    return b

def union(a, b):
    p[find(a)] = find(b)

def deepest():
    maxd = (0, None)
    for (a, pa) in p.items():
        d = 1
        while (pa in p):
            d += 1
            pa = p[pa]
        maxd = max(maxd, (d, a))
    return maxd[1]

def example(k):
    global count, p
    count = 0
    p.clear()
    for a in range(((2 ** k) - 1), 0, (- 1)):
        union(a, (a & (a - 1)))
    r = 0
    for a in range((2 ** k), (2 ** (k + 1))):
        union(r, a)
        find(deepest())
        r = a
example(9)
print(count)

или эта сложность чисто теоретическая, а не практическая?

да. сложность алгоритма — это чисто теоретическая конструкция для описания насколько хорошо алгоритм масштабируется при различных размерах входных данных (в данном случае, количестве находок и объединений).

Это не дает никаких гарантий относительно количества шагов, необходимых для конкретного экземпляра ввода (скажем: 5 находит и 3 объединения) — кроме конечного числа шагов. На самом деле большая нотация O использует понятие произвольно большой мультипликативной константы, что не помогает для расчета точного времени выполнения, но этого достаточно, чтобы различать алгоритмы по классам сложности.