神马文学网5 algorithms you must know - 刀目村的专栏 - CSDNBlog
来源：百度文库 编辑：神马文学网 时间：2024/04/28 09:02:51
Sorting - The most fundamental thing in algorithms,and it's almost a given. (And it means the same in English as it doesin Math, so no explanations needed, I hope.) There are tons of crazysorts 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 sortis important to learn, because it teaches us an important paradigm -you don't need to find an algorithm that does everything the best - usethe best algorithm for each test case!
Real World Application:You're in a library, given a bunch of books. You want be able to lookfor books without looking at every book every time. Sort them and doquick checks!
Binary Search- This is the classic example of Divide and Conquer. Remember that game20 questions? You have to ask 20 questions to guess a word. Well, theway to cheat is to narrow it down half way every time. The EnglishDictionary has about 500,000 words, meaning you would still havequeries 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.
Butits application doesn't stop there, as it (as well as its cousinternary search) can help you solve numerical equations (this isactually call bisection, but same paradigm). For example, you want tofind the cube root of N (N^(1/3)), but don't have some sort of libraryready. Easy solution? Binary search! You know x=y^3, so "guess" a valuefor x, and go from there!
Real World Application: According to folklore, Professor Skienawould demonstrate binary search by asking for a name, and then lookingit up in the phonebook by checking the middle of the book, does acomparison, and literally tear out half the book and throw it in thetrash. You can probably come up with a less dramatic example.
Hashing- Conceptually easy, if only because most classes hop over this withidealizations. The legendary Udi Manber was fond of saying, "hashing,hashing, hashing". No, real hashing is hard, but don't be afraid to useit. Imagine you have a closet full of shirts. It's very hard to find ashirt. So what can you do?
Hash it. Take every shirt, and put itin a different drawer depending on the color of the shirt. Whenever youwant a shirt, all you have to do is simply open the drawer with thecorresponding color. That's hashing in a nutshell.
Of course,you might (and likely) have more than one shirts of a given color. Thatis hash collision, and there are tons of research papers in the worldon the topic, so know that they exist.
To paraphrase, no one ever got fired for using a hashtable before!
RealLife Application: Gave one describing it above. You can use hashing onalmost 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'strivial to translate this recursively. So we do. Unforunately, if youwant to know, say, the 100-th Fibonacci number, and your computer does,say, a trillion calculations a second, it will still take, about 11years to get your answer. So save and reuse your results! If you did dothat, even if you only do 100 operation a second, it'll take less thana minute!
Yes, someone's going to point out you only need thelast 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'mhandwaving right now, but this isn't simply "saving down results", ofcourse. DP/Memo is when you know that certain results will be re-usedin the future, exploiting the fact that well, you don't need to redoingthe same thing over and over again..
Real Life Application: Youneed 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 againfor the other digits? You can if you want, but you saved yourself somework 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 canbe reduced into a graph, and knowing the best way to search a graphwill come in handy. DFS is basically a stack-based implementation,while BFS is a queue-based implementation, and each with its strengthand weaknesses.
Real Life Application: You have to get frompoint A to point B. You don't know if you can get there. So what do youdo? You drive and drive around until you hope to find the destination.Reach a deadend? Turn around and come back where you came from. Itmight 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 inthe "real world". It's true. If you're a codemonkey that codes exactlyto perfect specs everytime, you might never come across such a need.Knowing algorithmsand 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 attackthe same problem. Ultimately, anyone can look it up in a textbook orreference 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!
Real World Application:You're in a library, given a bunch of books. You want be able to lookfor books without looking at every book every time. Sort them and doquick checks!
Binary Search- This is the classic example of Divide and Conquer. Remember that game20 questions? You have to ask 20 questions to guess a word. Well, theway to cheat is to narrow it down half way every time. The EnglishDictionary has about 500,000 words, meaning you would still havequeries 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.
Butits application doesn't stop there, as it (as well as its cousinternary search) can help you solve numerical equations (this isactually call bisection, but same paradigm). For example, you want tofind the cube root of N (N^(1/3)), but don't have some sort of libraryready. Easy solution? Binary search! You know x=y^3, so "guess" a valuefor x, and go from there!
Real World Application: According to folklore, Professor Skienawould demonstrate binary search by asking for a name, and then lookingit up in the phonebook by checking the middle of the book, does acomparison, and literally tear out half the book and throw it in thetrash. You can probably come up with a less dramatic example.
Hashing- Conceptually easy, if only because most classes hop over this withidealizations. The legendary Udi Manber was fond of saying, "hashing,hashing, hashing". No, real hashing is hard, but don't be afraid to useit. Imagine you have a closet full of shirts. It's very hard to find ashirt. So what can you do?
Hash it. Take every shirt, and put itin a different drawer depending on the color of the shirt. Whenever youwant a shirt, all you have to do is simply open the drawer with thecorresponding color. That's hashing in a nutshell.
Of course,you might (and likely) have more than one shirts of a given color. Thatis hash collision, and there are tons of research papers in the worldon the topic, so know that they exist.
To paraphrase, no one ever got fired for using a hashtable before!
RealLife Application: Gave one describing it above. You can use hashing onalmost 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'strivial to translate this recursively. So we do. Unforunately, if youwant to know, say, the 100-th Fibonacci number, and your computer does,say, a trillion calculations a second, it will still take, about 11years to get your answer. So save and reuse your results! If you did dothat, even if you only do 100 operation a second, it'll take less thana minute!
Yes, someone's going to point out you only need thelast 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'mhandwaving right now, but this isn't simply "saving down results", ofcourse. DP/Memo is when you know that certain results will be re-usedin the future, exploiting the fact that well, you don't need to redoingthe same thing over and over again..
Real Life Application: Youneed 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 againfor the other digits? You can if you want, but you saved yourself somework 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 canbe reduced into a graph, and knowing the best way to search a graphwill come in handy. DFS is basically a stack-based implementation,while BFS is a queue-based implementation, and each with its strengthand weaknesses.
Real Life Application: You have to get frompoint A to point B. You don't know if you can get there. So what do youdo? You drive and drive around until you hope to find the destination.Reach a deadend? Turn around and come back where you came from. Itmight 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 inthe "real world". It's true. If you're a codemonkey that codes exactlyto perfect specs everytime, you might never come across such a need.Knowing algorithmsand 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 attackthe same problem. Ultimately, anyone can look it up in a textbook orreference 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!
5 algorithms you must know - 刀目村的专栏 - CSDNBlog
5 algorithms you must know
5 Wordpress Tips and Tricks You Must Know
你的生日含义，DO YOU KNOW ?
你的生日含义，DO YOU KNOW ?
我是一块声卡 - 刀目村的专栏 - CSDNBlog
Unix系统发展史 - 刀目村的专栏 - CSDNBlog
我是一个CPU - 刀目村的专栏 - CSDNBlog
我是一块主板 - 刀目村的专栏 - CSDNBlog
我是一条内存 - 刀目村的专栏 - CSDNBlog
[推荐]Did you Know?
what you never know
Do you know?
教育的未來(Did you know？) - 心理-Psychology Express-...
教育的未來(Did you know？)(Psytopic)
教育的未来（Did you know?） 转
年轻人要看的励志短片:《DID YOU KNOW》
C armman的专栏 - CSDNBlog
李嘉诚在汕头大学的讲话 - 刀目村的专栏 - CSDNBlog
学习Java的30个基本概念 - 刀目村的专栏 - CSDNBlog
Windows NT is VMS re-implemented? - 刀目村的专栏 - CSDNBlog
The Semantic Web - chs version - 刀目村的专栏 - CSDNBlog
The Semantic Web - eng version - 刀目村的专栏 - CSDNBlog
Microsoft Interview IQ questions - 刀目村的专栏 - CSDNBlog