Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 00:45, 29 October 2016

Revision as of 00:47, 29 October 2016

Line 70:

==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. Every 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'' − 2}} clusters that ever get added to the stack: {{math|''n''}} single-point clusters in the initial set, and {{math|''n'' − 2}} internal nodes other than the root in the binary tree representing the clustering. Therefore, the algorithm performs {{math|2''n'' − 2}} pushing iterations and {{math|''n'' − 1}} popping iterations,

Each of these iterations may eachspend time scanning as many as {{math|''n'' − 1}} inter-cluster distances to find the nearest neighbor.
The total number of distance calculations it makes is therefore less than {{math|3''n''²}},.
For andthe same reason, the total time itused usesby the algorithm outside of thethese distance calculations is {{math|O(''n''²)}}.

Since the only data structure is the set of active clusters and the stack containing a subset of the active clusters, the space required is linear in the number of input points.