[cfoley]

I was wondering what I can do to get better at designing algorithms. Searching the net dug up loads of tips and tricks to make code run faster but that's not what I want. An O(n^2) algorithm is still an O(n^2) algorithm after optimization. What I want is to make it O(n). Or O(1)!

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.

[KYA]

Well, here's some examples is pseudo code:

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.

[SixOfEleven]

There are entire semester courses taught on that. Efficiency can be hard to accomplish. It takes practice and learning how to think outside of the box. I know that is said a lot but it is true. Modelling a binary search is an excellent example. When you pick up a phone book, you open it in the middle. If you haven't found what you are looking for and it is before the page you open, you flip backwards half way, otherwise flip forward half way. Then repeat until you find what you are looking for. Looking at sorting and searching algorithms to see how they accomplish their task is a good start.

[cfoley]

Yeah I've done the courses but they don't train you in taking that inventive step. I know inventiveness is difficult to teach but there must be common strategies. Many sort algorithms use a divide and conquor approach. Search algorithms tend to rely on preorganisation of the data. Often some smart maths can turn something with nested loops into an O(1) algorithm.

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?

[SixOfEleven]

There is a book, Programming Pearls by Jon Bently. I remember reading it years ago. If I remember it correctly, it offers excellent in sight into these sorts of solutions. You can find it on Amazon.com or other book sites. It might be a good read.

[Dantheman]

An optimized O(n) algorithm may run 10 times as fast as non-optimized O(n) algorithm. Heck, sometimes an O(n^2) runs faster than O(n logn)! Don't think that a complexity and running time is the same thing.

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 NP-complete problems that are (currently) can't be solved in less than polynomial time.

Quote

Is there a good way to train my brain for those mental acrobatics?

Of course. Learn Math. Learn computational complexity theory.

This post has been edited by Dantheman: 05 June 2009 - 12:55 PM

[mikeblas]

Dantheman, on 5 Jun, 2009 - 11:42 AM, said:

An optimized O(n) algorithm may run 10 times as fast as non-optimized O(n) algorithm.

Yep.

Dantheman, on 5 Jun, 2009 - 11:42 AM, said:

Heck, sometimes an O(n^2) runs faster than O(n logn)! Don't think that a complexity and running time is the same thing.

Sometimes, but not hardly often enough!

Dantheman, on 5 Jun, 2009 - 11:42 AM, said:

For example, it is impossible to create a sorting algorithm that is better than O(n logn).

Hashing and counting sorting algorithms are better than O(nlogn). Radix sort, too.

SixOfEleven, on 5 Jun, 2009 - 11:37 AM, said:

There is a book, Programming Pearls by Jon Bently.

I'm not sure Pearls is really an algorithm book, but it's certainly good at stressing problem solving. That is, learning to think about problems in a way that gets the solution rather than following methods: the fastest sort isn't sorting at all, so let's see if we can solve this problem without sorting. And, it turns out, that you often can do that, and should try to find neat ways to avoid creating more problems than your solving.


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

[Dantheman]

Yes, mikeblas, I have made a mistake, claiming that sort algorithms can't be faster than O(n logn). This only applies to algorithms that use comparisons, they indeed cannot be faster than O(n logn). However, there are techniques, like the Radix sort that you've mentioned, that do not rely on comparisons.

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.

[cfoley]

Thanks for the responses guys. Very useful. I'll be sure to check out those books and look into discrete mathematics. In anyone has more insight then I'm still open to more responses!

[mikeblas]

If you're interested in discrete mathematics and computer science, I can't think of a better book than Concrete Mathematics.