경로 압축을 사용하지 않는 포리스트 구현이있는 비 연속 집합

Question

n 별개 요소가있는 가중치 결합 휴리스틱 (NO PATH COMPRESSION!) 만 사용하여 분리 집합의 포리스트 구현을 고려하십시오. n-1 개의 공용체 시퀀스를 실행하는 최악의 경우의 시간 복잡도를 T (n, m)로 정의하고 m은 임의의 순서로 찾습니다. 여기서 m은 n보다 큰 양의 정수입니다.

T (n, m)을 n-1 개의 공용체를 이루는 순서로 정의한 다음 가능한 가장 큰 트리에서 찾기 연산을 수행하는 것이 가장 길기 때문에 m은 AFTERWARDS를 찾습니다. 따라서 각 노동 조합이 O (1)을 취하여 n-1 개의 노동 조합이 n-1 단계가되기 때문에 T (n, m) = m * log (n) + n - 1이고 각 탐색은 n-1 노동 조합 후의 결과 트리의 높이는 log_2 (n)로 제한됩니다.

내 문제는 T (n, m)이 좋아 보이니?

둘째, T (n, m) Big Omega (m * log (n))입니까? 나의 주장은 가능한 최소의 T (n, m)이 m * log (2) + 1이고 m * log (2)보다 분명히 클 경우 c = 1이고 n> = 2라는 것이다. 이 질문을하는 것은 어리석은 것처럼 보입니다.하지만 해결책이 너무 쉬운 것 같아서 정확성에 대한 의문이 생깁니다.

미리 감사드립니다.

Answer 1

T (n, m)은 괜찮아 보이네요.하지만 최악의 경우는 찾기가 뒤 따르는 공식임을 증명할 수 있다고 생각합니다. T는 (N, m은) Ω (N m 로그())임을 증명에 관해서

, 당신은 N 및 m 와 C가 존재한다는 것을 보여줄 필요가되도록 모든 N ≥ N _{에 대한 0}이고 모두 m ≥ m 이면 T (n, m) ≥ cm log (n)을 유지합니다. 당신이 말한 것은 틀림없이 n = 2에 대해서만 이것을 보여줍니다.