关于算法分析/性能？
如图所示，我有以下结构来将壁橱“曲线”存储在“切片”中。 “曲线”由实现为双向链表的“节点”组成。
这是伪代码：
class Slice {
List<Curve*> curves;
}
class Curve {
int objectID;
Node *headNode;
}
class Node {
double x,
double y,
Node *next;
Node *previous
}
我使用 QT 绘制方法渲染此结构，并且我想选择最接近鼠标点的节点。
我所做的是，
a）。获取“切片”中的每个“曲线”
b）。遍历所选曲线中的所有节点，计算从鼠标点到每个点的距离并进行比较。
我的问题：
1）如果我们取曲线数量为“c”，平均节点为“n”，则算法复杂度为 O(n*c)。 这个分析正确吗？
2）有没有办法改进算法，使其更快？使用二叉树、哈希表等？
As show in the picture I have following structures to store set of closet "Curves" in a "Slice".
A "Curve" consist of "Nodes" implemented as a doubly-linked-list.
Here is the psuedo code :
class Slice {
List<Curve*> curves;
}
class Curve {
int objectID;
Node *headNode;
}
class Node {
double x,
double y,
Node *next;
Node *previous
}
I render this stucture using QT paint methods and I want to select the node closest to the mouse point.
What I do is,
a).Get each "Curve" in the "Slice"
b).Go through all nodes in selected curve and calculate the distance from mouse-point to each point and compare.
My questions :
1) if we take number of curve is "c" and average nodes is "n" the algorithm complexity is O(n*c).
Is this analysis correct?
2)Is there anyway to improve the algorithm ,make it more faster? Using Binary Tree,HashTable ..etc?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
1) 是的，您的分析是正确的
2) 您可以通过使用最近邻搜索算法。
最简单的可能是使用 kd 树
1) Yes your analysis is correct
2) You can get logarithmic complexity by using the nearest neighbor search algorithms.
The simplest of all is perhaps using the k-d tree