Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 04:26, 15 August 2021

Revision as of 07:26, 24 December 2021

Line 92:

==Time and space analysis==

Each iteration of the loop performs a single search for the nearest neighbor of a cluster, and either adds one cluster to the stack or removes two clusters from it. EveryEach cluster is only ever added once to the stack, because when it is removed again it is immediately made inactive and merged. There are a total of {{math|2''n'' &minus; 2}} clusters that ever get added to the stack: {{math|''n''}} single-point clusters in the initial set, and {{math|''n'' &minus; 2}} internal nodes other than the root in the binary tree representing the clustering. Therefore, the algorithm performs {{math|2''n'' &minus; 2}} pushing iterations and {{math|''n'' &minus; 1}} popping iterations.<ref name="murtagh-tcj"/>

Each of these iterations may spend time scanning as many as {{math|''n'' &minus; 1}} inter-cluster distances to find the nearest neighbor.