*This post originally available on my devblog.*Did you know computers are stupid machines? They are actually so stupid that they don't know how to multiply; instead, they add - whenever you say 2*5, the computer is really doing 2+2+2+2+2! What computers can, and have always been capable of, is executing things incredibly quickly. So even if it uses repeated addition, it adds so quickly that you don't even feel it adds repeatedly, it just spits out the answer as if it used its memory like you would have. However, fast as computers are, sometimes you need it to be faster, and that's what we're going to tackle in this article. But first, let's consider this: Here are 7 doors, and behind them are numbers, one of which contains a 36. If I asked you to find it, how would you do it? Well, what we'd do is open the doors, and hope we're lucky to get the number. Here we open 4 doors, and find 36. Of course, in the worst case scenario, if we were unlucky, we might have ended up opening all 7 doors before finally finding 36. Now suppose I give you a clue. This time, I tell you the numbers are sorted, from lowest to highest. You can instantly see that we can work on opening the doors more systematically: If we open the door in the middle, we know which half the number we are looking for is. In this case we see 24, and we can then tell that 36 should be in the latter half. We can take the concept even further, and - quite literally - divide our problem in half: In the picture above, instead of worrying about 6 more doors, we now only worry about 3. We again open the middle, and find 36 in it. In the worst case scenario, if we opened the doors wildly, or linearly, opening doors one by one without a care, we would have to open all doors to find what we are looking for. In our new systematized approach, we would have to open a significantly lower number of doors - even in the worst case scenario. This approach is logarithmic in running time, because we always divide our number of doors by half. Here is a graph of the doors we have to open, relative to the number of doors. See how much faster log n is, even on incredibly large input. On the worst case scenario, if we had 1000 doors and we opened them linearly, we would have to open all of them. If we leverage the fact that the numbers are sorted however, we could continually divide the problem in half, and drastically lowering that number. An Algorithm is a step-by-step procedure for solving a problem, and here we have two basic algorithms. As you have already seen, our second algorithm is faster than our first in the worst case scenario. We could classify them by running time, the time it needs to take to complete the problem, which we equated here by the numbers of doors opened (since you take time to open doors). The first algorithm, which is a linear search algorithm, would have to open ALL doors, so we say it's running time is O(n), (pronounced Big-Oh-of-n) where n is the number of doors (input). The second algorithm, which is a binary search algorithm, would have to open a logarithmic amount of doors, so we say it's running time is O(log n). In the so called O-Notation, O represents the time needed for your algorithm to complete the task in the worst case scenario. We haven't looked at the other side of the coin however. What about the best case scenario? In both of our algorithms, the best case scenario would be to find the what we're looking for in the very first door of course! So, in both our cases, the best case running time would be 1. In O-Notation, theta (O) represents the best case scenario. So in notation, we say O(1) Here is a table so far of our algorithms:[table][tr][td][/td][td]?[/td][td]O[/td][/tr] [tr][td]Linear Search[/td] [td]1[/td] [td]n[/td][/tr] [tr][td]Binary Search[/td] [td]1[/td] [td]log n[/td][/tr][/table] Now unless all you're going to write in your life are door problems the style of Monty Hall, then we need to study more interesting algorithms.

Sign in to follow this

Followers
0

#
Writing Fast Code: Introduction To Algorithms and Big-O

General and Gameplay Programming

Sign in to follow this

Followers
0