我正在做一个作业问题，简化后就是将恒星分为x，y坐标和最小距离，将其分成星座。任何恒星本身都可以是星座。因此，例如5颗星无法相互连接，那么它将返回有5个星座。
我最初制作了一种算法，使用O（n ^ 2）的运行时间检查每个点。我想使其更快，并看到DBSCAN在O（nlogn）时间中运行。
我的问题是，如果我要使用DBSCAN，该算法表示它将以O（nlogn）时间运行，但是如果我的minPts为1（群集的大小），则将否定DBSCAN的效率并以O运行（n ^ 2）??
就我而言，在这种情况下，DBSCAN的运行时间取决于邻居的计算，邻居的计算是在给定距离内对每个点进行的。如前所述，如果执行线性扫描，则总共将获得O（n ^ 2）。但是，为了加快搜索速度，您可以使用基于索引的结构，该结构以O（logn）时间进行搜索。请结帐spatial databases。
运行时取决于epsilon是否足够小以使结果大小较小，以及能够加速这些查询的索引。对分钟数没有要求，因此它适用于单链接群集的“简并”情况。
但是，在您的情况下，您可能只是想直接使用空间索引进行邻居搜索，而不是通过DBSCAN的代理？