Ashika Umanga Umagiliya
Ashika Umanga Umagiliya

Reputation: 9158

About algorithm analysis/performance?

enter image description here

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?

Upvotes: 4

Views: 140

Answers (1)

parapura rajkumar
parapura rajkumar

Reputation: 24403

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

Upvotes: 3

Related Questions