A Simpler Proof Of The Average Case Complexity Of Union-Find WithPath Compression

Wu, Kesheng ; Otoo, Ekow

Lawrence Berkeley National Laboratory

关键词: Data Analysis Union-Find Algorithms Analysis Of Algorithms Average Casecomplexity;    Union-Find Algorithms Analysis Of Algorithms Average Casecomplexity;    Algorithms;    Calculation Methods;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;   

DOI  :  10.2172/877676
RP-ID  :  LBNL--57527
RP-ID  :  DE-AC02-05CH11231
RP-ID  :  877676

美国|英语

来源: UNT Digital Library

【 摘 要 】

We present a modified union-find algorithm that represent the data in an array rather than the commonly used pointer-based data structures, and a simpler proof that the average case complexity of the union-find algorithm is linear.