Content deleted Content added
→Time and space analysis: Complexity of variants Tags: Reverted Mobile edit Mobile web edit |
|||
Line 100:
For the same reason, the total time used by the algorithm outside of these distance calculations is {{math|O(''n''<sup>2</sup>)}}.<ref name="murtagh-tcj"/>
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.<ref name="murtagh-tcj"/> However, an implementation using a pairwise distance matrix is often smaller, as every distance then is only computed once, and Lance-Williams-Equations can be used to reduce the cost of computing distances between clusters, at the cost of increasing memory requirements to quadratic memory. For the special case of squared Euclidean distance, cluster centers can replace the set of data points and also reduce the number of distance computations, while keepimg the memory usage linear.
Using index structures to accelerate nearest neighbor search - instead of scanning all other clusters - the algorithm can be used on many real data sets in subquadratic time with linear memory, however the theoretical worst case complexity does not improve and remains quadratic.
==Correctness==
| |||