five algorithms you must know.doc

5 algorithms you must know(2007-11-14 18:58)
分类： C语言相关

Sorting - The most fundamental thing in algorithms, and it's almost a given. (And it means the same in English as it does in Math, so no explanations needed, I hope.) There are tons of crazy sorts out there, but quick sort is the one everyone should be familiar with, merge sort is the one that comes in handy when you can't fit everything into RAM, and introspective sort is important to learn, because it teaches us an important paradigm - you don't need to find an algorithm that does everything the best - use the best algorithm for each test case!

Real World Application: You're in a library, given a bunch of books. You want be able to look for books without looking at every book every time. Sort them and do quick checks!

Binary Search - This is the classic example of Divide and Conquer. Remember that game 20 questions? You have to ask 20 questions to guess a word. Well, the way to cheat is to narrow it down half way every time. The English Dictionary has about 500,000 words, meaning you would still have queries to spare.

Yes, it would be boring, but it would go something like this:

Does your word come before the word "marry"? Yes
Does your word come before the word "gerrymander"?

You get the point.

Assuming you already know you have to sort, you can binary search at O(log_2 N). Which for say, a trillion, is less than 50.

But its application doesn't stop there, as it (as well as its cousin ternary search) can help you solve numerical equations (this is actually call bisection, but same paradigm). For example, you want to find the cube root of N (N^(1/3)), but don't have some sort of library ready. Easy solution? Binary search! You know x=y^3, so "guess" a value for x, and go from there!

Real World Application: According to folklore, Professor Skiena would demonstrate binary search by asking for a name, and then looking it up in the phonebook by checking the middle of the book, does a comparison, and literally tear out half the book and throw it in the trash. You can probably come up with a less dramatic example.

Hashing - Conceptually easy, if only because most classes hop over this with idealizations. The legendary Udi Manber was fond of saying, "hashing, hashing, hashing". No, real hashing is hard, but don't be afraid to use it. Imagine you have a closet full of shirts. It's very hard to find a shirt. So what can you do?

Hash it. Take every shirt, and put it in a different drawer depending on the color of the shirt. Whenever you want a shirt, all you have to do is simply open the drawer with the corresponding color. That's hashing in a nutshell.

Of course, you might (and likely) have more than one shirts of a given color. That is hash collision, and there are tons of research papers in the world on the topic, so know that they exist.

To paraphrase, no one ever got fired for using a hashtable before!

Real Life Application: Gave one describing it above. You can use hashing on almost anything, if you don't need to know the ordering.

Dynamic Programming - Sometimes it is known by its other name - Memoization. No, it is not memorization, no 'r'. Fine, its most common name is caching. Save your results so you don't have to do it again!

It's not always so dramatic, but how many times do you want to recalculate things? The classic example of the Fibonacci sequence is an example:

f( n ) = f( n - 1 ) + f( n - 2 )

It's trivial to translate this recursively. So we do. Unforunately, if you want to know, say, the 100-th Fibonacci number, and your computer does, say, a trillion calculations a second, it will still take, about 11 years to get your answer. So save and reuse your results! If you did do that, even if you only do 100 operation a second, it'll take less than a minute!

Yes, someone's going to point out you only need the last two numbers, so you can use a for loop. You're perfectly correct, and that's "Dynamic Programming" (DP). Sometimes memoization is faster, sometimes dp is faster. Experience will tell you which one is which.

I'm handwaving right now, but this isn't simply "saving down results", of course. DP/Memo is when you know that certain results will be re-used in the future, exploiting the fact that well, you don't need to redoing the same thing over and over again..

Real Life Application: You need to multiply say, 5123 x 3333 (yes, it's an obvious example) without using calculator etc. Well, you work out that 5123 x 3 = 15369. What do you do? Write it down. Do you have to multiply 5123 x 3 again for the other digits? You can if you want, but you saved yourself some work because you wrote it down!

Search Algorithm - This is relatively generic. The two most common is Depth-First Search (DFS)and Breadth-First Search (BFS). Understanding these leads to you more exotic things like A* Search, and it's a fundamental exploring algorithm. Too many things can be reduced into a graph, and knowing the best way to search a graph will come in handy. DFS is basically a stack-based implementation, while BFS is a queue-based implementation, and each with its strength and weaknesses.

Real Life Application: You have to get from point A to point B. You don't know if you can get there. So what do you do? You drive and drive around until you hope to find the destination. Reach a deadend? Turn around and come back where you came from. It might not be the shortest way, but if you tried every possible road, you'll know that maybe you can't get to China from New York. Whoops. (And that's a DFS!)

When people think of algorithms, there will be people who will keep saying how rarely they use them in the "real world". It's true. If you're a codemonkey that codes exactly to perfect specs everytime, you might never come across such a need. Knowing algorithms and what to do the rare times you need to is a valuable tool. Besides, it's about learning the tools and different ways to think and attack the same problem. Ultimately, anyone can look it up in a textbook or reference book, but understanding algorithms will allow you to solve problems that aren't as flexible as the textbook.

So read up, good luck, and maybe actually implement them!