9 Replies  1831 Views  Last Post: 08 June 2009  08:44 PM
#1
How to design faster algorithms?
Posted 05 June 2009  09:12 AM
I guess problem solving skills and experience are the most important but there must be some strategies that work for large numbers of problems. (e.g. preorganising data).
So, please share your tips and tricks.
Replies To: How to design faster algorithms?
#2
Re: How to design faster algorithms?
Posted 05 June 2009  10:36 AM
for(int i = 0; i < n; i++) { //stuff }
This is linear O(n). Not much you can do with that if you HAVE to traverse the whole array. The idea would be to come up with another way to look up the info you want rather then go through everything. This would apply to any algorithm. For example the n^2 bubblesort:
for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { } }
In and of itself, we could make it a bit better by having j be > i in the iteration, but it is still of bubblesort quality.
To optimize, we want to look at faster/better ways to go through data. For example: if the bubblesort is too slow, I could try a quick or merge sort.
#3
Re: How to design faster algorithms?
Posted 05 June 2009  10:43 AM
#4
Re: How to design faster algorithms?
Posted 05 June 2009  11:27 AM
A toolbox of things to consider would be awesome but there's still that inventive step. Is there a good way to train my brain for those mental acrobatics?
#5
Re: How to design faster algorithms?
Posted 05 June 2009  12:37 PM
#6
Re: How to design faster algorithms?
Posted 05 June 2009  12:42 PM
Besides, some algorithms are impossible to achieve a better complexity. For example, it is impossible to create a sorting algorithm that is better than O(n logn). Threre's is a whole class of NPcomplete problems that are (currently) can't be solved in less than polynomial time.
Quote
Of course. Learn Math. Learn computational complexity theory.
This post has been edited by Dantheman: 05 June 2009  12:55 PM
#7
Re: How to design faster algorithms?
Posted 06 June 2009  03:05 AM
Dantheman, on 5 Jun, 2009  11:42 AM, said:
Dantheman, on 5 Jun, 2009  11:42 AM, said:
Dantheman, on 5 Jun, 2009  11:42 AM, said:
SixOfEleven, on 5 Jun, 2009  11:37 AM, said:
Skenia recently published a new edition of his Algorithm Design Manual book, which is an outstanding reference for understanding the different techniques for designing algorithms. The Levetin book isn't bad, either.
This post has been edited by mikeblas: 06 June 2009  03:07 AM
#8
Re: How to design faster algorithms?
Posted 06 June 2009  09:10 AM
By the way, I have Levitin's book on algorithms. It is a great material. However, before buying it, make sure you at least took a Discrete Math course and know how to use the data structures, like Trees, Maps, and Graphs.
#9
Re: How to design faster algorithms?
Posted 08 June 2009  01:30 PM
#10
Re: How to design faster algorithms?
Posted 08 June 2009  08:44 PM
