![]() By studying growth vs input size, we can ignore device-specific details and actually measure the algorithm, instead of the specific combination of algorithm and computer. You will notice the number of digits (d) is the exponent in this equation, and as such we say this is an exponential time algorithm, and that the running time grows exponentially with the length of the input.ĭifferent computers have different strengths certain operations might be faster on one computer than another. Assuming the time taken to guess each digit takes the same amount of time (regardless of the length), we can represent this mathematically like so: a secret number with 1 digit has 10 possible values (0, 1, 2, 3, 4, 5, 6, 7, 8 & 9), and a secret number with 2 digits has 100 possible values. The question now becomes: How does the number of possible combinations grow with the length of the secret number?Įach digit we add to our secret number multiplies the number of possible combinations by 10. On average, we’d have to try around half the possible inputs, so the running time of our algorithm is proportional to the number of possible combinations. How long would this take? Now, in theory we could get lucky and guess the answer in one go, but this is very unlikely. Since we have no information about what that number might be, the best algorithm to find this secret number uses a ‘brute-force’ method, which means it does nothing clever and simply tries every possible number. Let’s say the only way we can check if our answer is correct is by punching it into a keypad. In this case, the size of the problem is the length of the number. Let’s say I have a secret number (such as a PIN), and the problem is to guess it. Here is one final example that is very particularly interesting to us. But whether you can do a million operations a second or just one, the rate of growth will be the same. grows with the square of the length of the input number (quadratic time)Īgain, different computers will execute this algorithm at different speeds a laptop can perform addition millions of times faster than a human can. ![]() The computer repeats this until there are no more digits to add, and the algorithm ends. It then moves one digit to the left (carrying over a ‘1’ if the result was greater than 9) and repeats the process. When adding two multi-digit numbers, a common algorithm you probably learnt at school starts with the rightmost digit from each number and adds them together. In this case the output will be a new number. This time, the input is two numbers of equal length, and the problem is to add them together. It might take different computers different amounts of time to get this result, but that’s due to other factors and not the length of the input. We call this a constant time algorithm, because the time the algorithm takes to complete doesn't depend on the size of the input number. In this case, the ‘input’ is a number, and the output is either ‘Even’ or ‘Odd’. ![]() ![]() For example, an algorithm that decides if a number is even only needs to look at the last digit in that number. In computer science, we classify algorithms on how the resources they use grow with the size of the input. To understand the role of quantum computers amongst modern traditional computers, we first need to learn how we measure the performance of different algorithms. In this course, we will only consider computers in their simplest form no keyboards, mice, or screens- just information and algorithms. We call these sets of instructions algorithms, and a lot of the research into computers is into the behaviour of different algorithms. The instructions we give computers need to be very specific and unambiguous. It seems computers can do anything! These systems can be very complex and specialised, but they all have one thing in common: A computer carries out a set of instructions on some input information to give us some new (output) information. Today, computers take many forms: From laptops and phones to the systems controlling traffic lights. Seeing as you’ve managed to access this webpage, you should already know what a computer is.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |