## 3 The Proposed Algorithm
### Complexity Analysis  
Computational complexity is an important metric for evaluating the performance of an algorithm. In the previous subsections, all phases of the algorithm were described in detail. In this section, the time complexity of the algorithm is analyzed. In the partitioning phase, it is assumed that the size of the dataset is \(N\). First, calculating the density profiles in all dimensions using the kernel density estimation function requires \(O(N*m)\), where \(N\) is the number of data points and \(m\) is the grid points. After obtaining the density profile, building a Kd-Tree to accelerate the search for nearest-neighbor points and assigning them to the nearest-neighbor crest index takes \(O(NlogP)\), where \(P\) is the number of crests, and the time complexity of partitioning the subclusters is \(O(V*P)\), with \(V\) denoting the dimension. In the merging phase, it takes \(O(logN)\) to compute the shared k-nearest neighbors among subclusters, \(O(n^{2})\) time complexity to compute the similarity among  
Figure 6: The process of simultaneously merging subclusters with maximum similarity. subclusters, and \(O(n*logn)\) to iteratively merge the subclusters, where \(n\) is the number of subclusters. In summary, the total time complexity of the algorithm is \(O(N*m+N*logP+V*P+logN+N^{2}+n*logn)\), which can be approximated as \(O(NlogP)\). This is because when analyzing the time complexity of an algorithm, we usually look for the highest-order terms, since the highest-order terms will dominate the growth rate of the whole expression when the input size \(N\) becomes very large. Next, we will analyze why the time complexity is approximated as \(O(NlogP)\). ```
1:Subclusters \(Sub\_final\),Noise
2:Label
3:Initialize \(Similarity\_matrix=[\ ]\), Label =[ ]
4:for each cluster \(c\in Sub\_final\)do
5: Calculate \(KNN\_count\) and \(RKNN\_count\) for \(c\) according to Equation (5)
6:endfor
7:for each pair \((cluster1,cluster2)\in combinations(clusters,2)\)do
8: Calculate \(shared\_KNN\_count\) for cluster1 and cluster2 according to Equations (7) and (8)
9: Calculate \(similarity\) between \(cluster1\) and \(cluster2\) according to Equation (9)
10: Store \(similarity\) in \(similarity\_matrix\) with key \((cluster1,cluster2)\)
11:endfor
12:while\(clusters>1\)do
13: Initialize \(merge\_list=[\ ]\)
14:for each pair \((cluster1,cluster2)\in combinations(clusters,2)\)do
15:if\(similarity\_matrix[(cluster1,cluster2)]>max\_similarity\)then
16:\(max\_similarity=similarity\_matrix[(cluster1,cluster2)]\)
17:\(merge\_list=[(cluster1,cluster2)]\)
18:elseif\(similarity\_matrix[(cluster1,cluster2)]==max\_similarity\)then
19: Append \((cluster1,cluster2)\) to \(merge\_list\)
20:endif
21:endfor
22:for each pair \((cluster1,cluster2)\in merge\_list\)do
23:\(merge\_cluster=merge\_clusters(cluster1,cluster2)\)
24: Remove \(cluster1\) from \(clusters\)
25: Remove \(cluster2\) from \(clusters\)
26: Append \(merged\_cluster\) to \(clusters\)
27: Update \(similarity\_matrix\) with new \(merged\_cluster\)
28:endfor
29:endwhile
30:Initialize \(Label=[\ ]\)
31:for\(index,cluster\in enumerate(clusters)\)do
32:for\(data\_point\in cluster\)do
33:\(Label[data\_point]=index\)
34:endfor
35:endfor
36:for each \(noise)\in Noise\)do
37: Assign the \(noise\) to the nearest \(cluster\)
38:\(Label[noise]=index\) of the nearest \(cluster\)
39:endfor
40:return\(Label\)
```  
**Algorithm 2** Merging strategies based on shared nearest neighbors  
First, the term \(O(N*m)\) depends on the value of \(\mathsf{m}\). If \(m\) is a constant, then \(N*m\) is \(O(N)\). However, regardless of the value of \(m\), \(N*m\) will not exceed \(O(N^{2})\). For \(O(N*logP)\), when \(P\) is a constant, it is denoted as \(O(N)\); otherwise! it remains below \(O(N^{2})\). Similarly, \(O(V*P)\), \(O(logN)\) and \(O(n*logn)\) are all below \(O(N^{2})\). Consequently, the time complexity can be approximated as \(O(NlogP)\). The above-mentioned \(O\) denotes a mathematical notation used to describe an upper bound on the growth rate of a function.