blob: e73595a4fe7c4c0e5132a3a73538449df681be78 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
---
id: Complexity
aliases:
- Computational/Time Complexity
tags: []
---
## Computational/Time Complexity
- K-Medoids:
- PAM: $O(K(n - k)^2)$
- Kernel K-Means:
- Computational complexity (time and space) is higher than K-Means
- Need to compute and store n x n kernel matrix generated from the kernel
function on the original data, where n is the number of points
- Hierarchical Clustering:
- Agglomerative Clustering
- Time complexity: $O(n^2)$
- Algorithmic Complexity: $O(m^2logm)$
- Density-based Clustering:
- DBSCAN:
- Computational complexity: $O(nlogn)$
- worst case: $O(n^2)$
- OPTICS:
- Complexity: $O(NlogN)$
|
