关于算法分析/性能？

Question

​

​

如图所示，我有下面的结构来存储一组壁橱“曲线”在“切片”。“曲线”由实现为双向链表的“节点”组成。

下面是psuedo代码：

class Slice {
 List<Curve*> curves;
}

class Curve {
 int objectID;
 Node *headNode;
}

class Node {
 double x,
 double y,
 Node *next;
 Node *previous
}

我使用QT画图方法渲染这个结构，我想选择离鼠标点最近的节点。

我要做的是，

a).Get“切片”中的每条“曲线”

b).Go遍历所选曲线中的所有节点，并计算鼠标点到每个点的距离并进行比较。

我的问题：

1)当曲线个数为"c“，平均节点数为"n”时，算法复杂度为O(n*c)。这个分析正确吗？

2)有没有办法改进算法，使其更快？使用二叉树，HashTable ..etc？

Answer 1

1)是的，你的分析是正确的

2)使用算法可以得到对数复杂度。

最简单的可能就是using the k-d tree了