So I encountered some problems in my centroid calculation algorithm, which I am trying to correct but I really wanted to see why am I implementing the algorithm that I have mentioned in the last to last post rather than the naive algorithm.
This gives a time complexity of O(n log n) over naive O(n^2) which would have certainly been easier. But I think this would save appreciable computational cycles.
Assuming that we are working with 4000nodes. And considering the average number of children a node has to be 8. Then here are the comparisons.
Naive Algorithm.
64 X 4000 = 256,000
New algorithm.
24 X 4000 = 96,000
This is difficult to code, requires extreme patience and there are so many cases ; I need to finish it fast.
This gives a time complexity of O(n log n) over naive O(n^2) which would have certainly been easier. But I think this would save appreciable computational cycles.
Assuming that we are working with 4000nodes. And considering the average number of children a node has to be 8. Then here are the comparisons.
Naive Algorithm.
64 X 4000 = 256,000
New algorithm.
24 X 4000 = 96,000
Here are the steps in the new in-centroid calculation.
- Get the maximally separated nodes.
(This is the part where I really used some clever techniques.)
- Choose one of them as zero and the other's direction as the positive x-axis.
- Transform the coordinates.
- Calculate the normal mean on the transformed coordinates.
- Transform back.
This is difficult to code, requires extreme patience and there are so many cases ; I need to finish it fast.
No comments:
Post a Comment