Algorithm Analysis
Download 14.03 Kb.
|
- Navigate this page:
- Algorithm Analysis
Algorithm Analysis This video is about Algorithm Analysis. [Slide 1] What do we mean by Algorithm Analysis? Well, we mean to develop an understanding of the characteristics of the algorithm used for different input parameters. Why would we want to do that? Algorithm analysis helps us predict the performance of algorithms. It helps us compare different algorithms and helps us choose good algorithms. Frequently there is more than one type of solution to every problem. Take sorting; remember that long list of sorting algorithms from the sorting video. There was insertions sort, bubble sort, merge sort, selection sort, quick sort. Each one of those uses a different algorithmic method. If you do algorithm analysis you’ll develop a good understanding of how the algorithm works. This also leads to improvement in your algorithms. They become shorter, simpler and more elegant. [Slide 2] When we do algorithm analysis we actually are thinking about computational complexity. What is computational complexity? It’s just a way to analyze an algorithm. It takes into account how difficult or how efficient or how fast the algorithm is. You usually evaluate it in terms of the amount of time that the algorithm takes, which we call time complexity; and the amount of memory that the algorithm takes, which we call space complexity. [Slide 3] Let’s look at time complexity. In terms of algorithms the time an algorithm takes is basically equal to the number of operations that are in the algorithm. When we do time complexity we want it to be independent of the programming language and the computer used. We can do this by remembering that algorithms are a sequence of steps or operations or commands. The more steps or operations there are in an algorithm the longer the algorithm takes to run. Our measure of time is actually a measure of the numbers of operations. [Slide 4] So what is an operation? An operation is anything that uses an arithmetic operation like addition, subtraction, multiplication, division. When you compare two items that’s an operation, when you swap two items that’s an operation, when you copy or save something to the disk to your hard drive that’s an operation. Accessing a list or reading something in memory is an operation. And how many times you go through a loop will affect the number of operations. [Slide 5] When you’re looking at a sorting algorithm you’re looking at comparing operations, so each comparison is one operation. And swapping or copying operations, where each swap or copy is an operation. When you’re looking at searching algorithms; when you’re comparing two items that’s an operation. [Slide 6] How do you figure out what the time complexity is? There are two ways to do it. One is that you can do a calculation. You can look at the basic loop for each of the algorithms or the basic recursive function. You can count the number of operations that occur in each loop or recursive function and put a time value to that. Then figure out how times the loop has run. Or you can run the program for different types or amounts of inputs. [Slide 7] You end up looking at a best, worst, or average case. The best case is the case of the time complexity of solving the program with the best input size. The worst case uses the worst input size, and the average case is just the average amount of time it takes to run any problem. [Slide 8] Let’s take a look at the time complexity for the two search algorithms we saw in the search algorithm video. We were looking at linear search and binary search time complexity. We’re not going to really focus on the best case because that’s really trivial. On the best case for a search you’d find the item you’re looking for the very first time you look. We know that’s really unlikely. We’re also not going to focus too much on the average case because one, it’s awfully too fickle to calculate. It’s not always the worst case divided by two. It can be very nonlinear. We’re going to focus on the worst case, so you can calculate the worst case search for both the linear search and the binary search. You can derive an equation that’s dependent on the list size, “N” in this case. For a linear search we know that the worst case situation is the list size itself. In a binary search because you keep dividing the list by two, it ends of that the worst case search for a binary search is log base two of the list size “N” and then you would add one to that value. If we had a list size of a thousand, then the worst case search for the linear search would be a thousand searches. The worst case search for a binary search would be ten searches. That’s how you would look at time complexity for algorithms.
While computational complexity is extremely important, you have to remember to think about the whole problem. [Slide 11] In summary, algorithm analysis involves looking at the characteristics of the algorithm for different inputs; that’s types of input and input size. You do that so you can predict the performance, compare algorithms and choose good algorithms. Also understanding how the algorithm works leads to improvements in your algorithm. We usually use computational complexity when we analyze algorithms. This measures how difficult your algorithm is and how efficient it is. We look at the time complexity or the amount of time that the algorithm takes, which is equal to the number of operations. And the space complexity, or the amount of memory the algorithm uses. There’s often a time/space tradeoff where you have to compromise on one or the other. Other things you think about when you do algorithm analysis is how difficult the algorithm is to understand, implement and modify. Will you be able to validate the algorithm easily, and is it suitable to the problem overall. Thank you.
Directory: files files -> Answer True False 2 points Question 2 files -> Integer programming and game theory files -> 4 Integer Programming files -> Bpa vehicle Window Repair Scenario #1 task: Procure vehicle window relacement. Objective files -> Pop Warner History files -> North Carolina Inclusion Initiative Mapping Where Children with ieps are Being Served Purpose files -> Fall 2013 Spring 2014 Program Data: Standard 1 Exhibit 4d files -> Hanban – asia society confucius classrooms network 2010 request for proposal files -> Northern England’s set-jetting locations Download 14.03 Kb. Share with your friends:
|