I don't have time to look to closely, but the only comment I have from a quick look is that you don't need your Point class. Just use the one that is already in Java.
Thread: Analysis of my program  |
|||||||||||||
|
Started 5 months ago by NoobTech
Hi,
I was working on this program where I have to take in a list of points from the user and plot them in such a was such that the plotter hand has to move the minimum distance(ie. I have to find the shortest distance for traversing all the points).
What is the time complexity of my program??? Also any suggestions to improve the performance would be highly appreciated....
|
|
||||||||||||
|
|||||||||||||
Other posts in this thread:
Lux Perpetua replied 5 months ago
Quote: Originally Posted by NoobTech Hi,
I was working on this program where I have to take in a list of points from the user and plot them in such a was such that the plotter hand has to move the minimum distance(ie. I have to find the shortest distance for traversing all the points).
What is the time complexity of my program??? Also any suggestions to ...
Size: 1,280 bytes
Customize: 
NoobTech replied 5 months ago
Quote: Originally Posted by Lux Perpetua Sorry, I don't think your program even works. You're using a greedy algorithm, and greedy algorithms are known not to work for the traveling salesman problem. It will not always find the shortest possible path.
The planar traveling salesman problem is a little bit better than the general case (because of the triangle ...
Size: 8,497 bytes
Customize:
NoobTech replied 5 months ago
After reading up a bit on Time complexities on the net. I am approximating the time complexity of my program to 2n^2+(n-1).
2n^2 for the 2 nested while loops that I have.
And (n-1) for comparing all the paths I get overall to get shortest path.
I have not taken into consideration the extra while loop in the else condition of the findClosestPoint method because this code will not ...
Size: 639 bytes
Customize:
Lux Perpetua replied 5 months ago
Quote: Originally Posted by NoobTech After reading up a bit on Time complexities on the net. I am approximating the time complexity of my program to 2n^2+(n-1). In what units?
Usually, people express time complexity in big-O notation to avoid having to worry about such things; then you could just say O(n^2) (which does seem to be the right answer, if I'm not...
Size: 808 bytes
Customize:
Lux Perpetua replied 5 months ago
Quote: Originally Posted by NoobTech Please advise if this is ok. And if not then how should I proceed. It depends on what "ok" means. If it means you have to find the actual shortest path, then I don't think it is. If it means you can use a suboptimal path as long as you can find it quickly, then it might be.
I could be wrong about that, by the way; it's ...
Size: 1,272 bytes
Customize:
NoobTech replied 5 months ago
Well if I do that, I will be making a lot of calculations using the Pythagoras theorem.
I have managed to get the distance of every point with every other point as well as the nearest point to every point with 2 nested for loops.
So this saves on a lot of computation when I am actually traversing and finding possible shortest paths using closest points.
Size: 438 bytes
Customize:
frger replied 1 month, 3 weeks ago
It's been ages since I did Java programming.
Size: 100 bytes
Customize:
|
Top contributing authorsRelated threads on "Dev Shed Forums - Open Source web development":Related threads on other sites: |
||||||||||||
Thread profile page for "Analysis of my program" on http://www.devshed.com.
This report page is a snippet summary view from a single thread "Analysis of my program", located on the Message Board at http://www.devshed.com.
This thread profile page shows the thread statistics for: Total Authors, Total Thread Posts, and Thread Activity
Home |
About Us |
Submit Your Site |
Update Your Site |
Get Search For Your Site |
Partners |
Contact |
Search Plugin |
Blog |
 |
Last Searches | Top Searches |
Designated brands and trademarks are property of their respective owners.
Use of this website constitutes acceptance of BoardReader's User Agreement and Privacy Policy.