Algorithm Analysis
Objectives
- To understand why algorithm analysis is important.
- To be able to use “Big-O” to describe execution time.
- To understand the “Big-O” execution time of common operations on Python lists and dictionaries.
- To understand how the implementation of Python data impacts algorithm analysis.
- To understand how to benchmark simple Python programs.
What Is Algorithm Analysis?
It is very common for beginning computer science students to compare their programs with one another. You may also have noticed that it is common for computer programs to look very similar, especially the simple ones. An interesting question often arises. When two programs solve the same problem but look different, is one program better than the other?
In order to answer this question, we need to remember that there is an important difference between a program and the underlying algorithm that the program is representing. As we stated in Chapter 1, an algorithm is a generic, step-by-step list of instructions for solving a problem. It is a method for solving any instance of the problem such that given a particular input, the algorithm produces the desired result. A program, on the other hand, is an algorithm that has been encoded into some programming language. There may be many programs for the same algorithm, depending on the programmer and the programming language being used.
To explore this difference further, consider the function shown in ActiveCode 1. This function solves a familiar problem, computing the sum of the first n integers. The algorithm uses the idea of an accumulator variable that is initialized to 0. The solution then iterates through the n integers, adding each to the accumulator.
1
def sumOfN(n):
2
theSum = 0
3
for i in range(1,n+1):
4
theSum = theSum + i
5
6
return theSum
7
8
print(sumOfN(10))
9
Now look at the function in ActiveCode 2. At first glance it may look strange, but upon further inspection you can see that this function is essentially doing the same thing as the previous one. The reason this is not obvious is poor coding. We did not use good identifier names to assist with readability, and we used an extra assignment statement during the accumulation step that was not really necessary.
1
def foo(tom):
2
fred = 0
3
for bill in range(1,tom+1):
4
barney = bill
5
fred = fred + barney
6
7
return fred
8
9
print(foo(10))
10
The question we raised earlier asked whether one function is better than another. The answer depends on your criteria. The function
sumOfN
is certainly better than the function foo
if you are concerned with readability. In fact, you have probably seen many examples of this in your introductory programming course since one of the goals there is to help you write programs that are easy to read and easy to understand. In this course, however, we are also interested in characterizing the algorithm itself. (We certainly hope that you will continue to strive to write readable, understandable code.)
Algorithm analysis is concerned with comparing algorithms based upon the amount of computing resources that each algorithm uses. We want to be able to consider two algorithms and say that one is better than the other because it is more efficient in its use of those resources or perhaps because it simply uses fewer. From this perspective, the two functions above seem very similar. They both use essentially the same algorithm to solve the summation problem.
At this point, it is important to think more about what we really mean by computing resources. There are two different ways to look at this. One way is to consider the amount of space or memory an algorithm requires to solve the problem. The amount of space required by a problem solution is typically dictated by the problem instance itself. Every so often, however, there are algorithms that have very specific space requirements, and in those cases we will be very careful to explain the variations.
As an alternative to space requirements, we can analyze and compare algorithms based on the amount of time they require to execute. This measure is sometimes referred to as the “execution time” or “running time” of the algorithm. One way we can measure the execution time for the function
sumOfN
is to do a benchmark analysis. This means that we will track the actual time required for the program to compute its result. In Python, we can benchmark a function by noting the starting time and ending time with respect to the system we are using. In the time
module there is a function called time
that will return the current system clock time in seconds since some arbitrary starting point. By calling this function twice, at the beginning and at the end, and then computing the difference, we can get an exact number of seconds (fractions in most cases) for execution.
Listing 1
import time
def sumOfN2(n):
start = time.time()
theSum = 0
for i in range(1,n+1):
theSum = theSum + i
end = time.time()
return theSum,end-start
Listing 1 shows the original
sumOfN
function with the timing calls embedded before and after the summation. The function returns a tuple consisting of the result and the amount of time (in seconds) required for the calculation. If we perform 5 invocations of the function, each computing the sum of the first 10,000 integers, we get the following:>>>for i in range(5):
print("Sum is %d required %10.7f seconds"%sumOfN(10000))
Sum is 50005000 required 0.0018950 seconds
Sum is 50005000 required 0.0018620 seconds
Sum is 50005000 required 0.0019171 seconds
Sum is 50005000 required 0.0019162 seconds
Sum is 50005000 required 0.0019360 seconds
We discover that the time is fairly consistent and it takes on average about 0.0019 seconds to execute that code. What if we run the function adding the first 100,000 integers?
>>>for i in range(5):
print("Sum is %d required %10.7f seconds"%sumOfN(100000))
Sum is 5000050000 required 0.0199420 seconds
Sum is 5000050000 required 0.0180972 seconds
Sum is 5000050000 required 0.0194821 seconds
Sum is 5000050000 required 0.0178988 seconds
Sum is 5000050000 required 0.0188949 seconds
>>>
Again, the time required for each run, although longer, is very consistent, averaging about 10 times more seconds. For
n
equal to 1,000,000 we get:>>>for i in range(5):
print("Sum is %d required %10.7f seconds"%sumOfN(1000000))
Sum is 500000500000 required 0.1948988 seconds
Sum is 500000500000 required 0.1850290 seconds
Sum is 500000500000 required 0.1809771 seconds
Sum is 500000500000 required 0.1729250 seconds
Sum is 500000500000 required 0.1646299 seconds
>>>
In this case, the average again turns out to be about 10 times the previous.
Now consider ActiveCode 3, which shows a different means of solving the summation problem. This function,
sumOfN3
, takes advantage of a closed equation ∑ni=1i=(n)(n+1)2 to compute the sum of the first n
integers without iterating.
1
def sumOfN3(n):
2
return (n*(n+1))/2
3
4
print(sumOfN3(10))
5
If we do the same benchmark measurement for
sumOfN3
, using five different values for n
(10,000, 100,000, 1,000,000, 10,000,000, and 100,000,000), we get the following results:Sum is 50005000 required 0.00000095 seconds
Sum is 5000050000 required 0.00000191 seconds
Sum is 500000500000 required 0.00000095 seconds
Sum is 50000005000000 required 0.00000095 seconds
Sum is 5000000050000000 required 0.00000119 seconds
There are two important things to notice about this output. First, the times recorded above are shorter than any of the previous examples. Second, they are very consistent no matter what the value of
n
. It appears that sumOfN3
is hardly impacted by the number of integers being added.
But what does this benchmark really tell us? Intuitively, we can see that the iterative solutions seem to be doing more work since some program steps are being repeated. This is likely the reason it is taking longer. Also, the time required for the iterative solution seems to increase as we increase the value of
n
. However, there is a problem. If we ran the same function on a different computer or used a different programming language, we would likely get different results. It could take even longer to perform sumOfN3
if the computer were older.
We need a better way to characterize these algorithms with respect to execution time. The benchmark technique computes the actual time to execute. It does not really provide us with a useful measurement, because it is dependent on a particular machine, program, time of day, compiler, and programming language. Instead, we would like to have a characterization that is independent of the program or computer being used. This measure would then be useful for judging the algorithm alone and could be used to compare algorithms across implementations.
Big-O Notation
When trying to characterize an algorithm’s efficiency in terms of execution time, independent of any particular program or computer, it is important to quantify the number of operations or steps that the algorithm will require. If each of these steps is considered to be a basic unit of computation, then the execution time for an algorithm can be expressed as the number of steps required to solve the problem. Deciding on an appropriate basic unit of computation can be a complicated problem and will depend on how the algorithm is implemented.
A good basic unit of computation for comparing the summation algorithms shown earlier might be to count the number of assignment statements performed to compute the sum. In the function
sumOfN
, the number of assignment statements is 1 (theSum=0) plus the value of n (the number of times we perform theSum=theSum+i). We can denote this by a function, call it T, where T(n)=1+n. The parameter n is often referred to as the “size of the problem,” and we can read this as “T(n) is the time it takes to solve a problem of size n, namely 1+n steps.”
In the summation functions given above, it makes sense to use the number of terms in the summation to denote the size of the problem. We can then say that the sum of the first 100,000 integers is a bigger instance of the summation problem than the sum of the first 1,000. Because of this, it might seem reasonable that the time required to solve the larger case would be greater than for the smaller case. Our goal then is to show how the algorithm’s execution time changes with respect to the size of the problem.
Computer scientists prefer to take this analysis technique one step further. It turns out that the exact number of operations is not as important as determining the most dominant part of the T(n) function. In other words, as the problem gets larger, some portion of the T(n) function tends to overpower the rest. This dominant term is what, in the end, is used for comparison. The order of magnitude function describes the part of T(n) that increases the fastest as the value of n increases. Order of magnitude is often called Big-O notation (for “order”) and written as O(f(n)). It provides a useful approximation to the actual number of steps in the computation. The function f(n) provides a simple representation of the dominant part of the original T(n).
In the above example, T(n)=1+n. As n gets large, the constant 1 will become less and less significant to the final result. If we are looking for an approximation for T(n), then we can drop the 1 and simply say that the running time is O(n). It is important to note that the 1 is certainly significant forT(n). However, as n gets large, our approximation will be just as accurate without it.
As another example, suppose that for some algorithm, the exact number of steps is T(n)=5n2+27n+1005. When n is small, say 1 or 2, the constant 1005 seems to be the dominant part of the function. However, as n gets larger, the n2 term becomes the most important. In fact, when n is really large, the other two terms become insignificant in the role that they play in determining the final result. Again, to approximate T(n) as n gets large, we can ignore the other terms and focus on 5n2. In addition, the coefficient 5 becomes insignificant as n gets large. We would say then that the function T(n) has an order of magnitude f(n)=n2, or simply that it is O(n2).
Although we do not see this in the summation example, sometimes the performance of an algorithm depends on the exact values of the data rather than simply the size of the problem. For these kinds of algorithms we need to characterize their performance in terms of best case, worst case, oraverage case performance. The worst case performance refers to a particular data set where the algorithm performs especially poorly. Whereas a different data set for the exact same algorithm might have extraordinarily good performance. However, in most cases the algorithm performs somewhere in between these two extremes (average case). It is important for a computer scientist to understand these distinctions so they are not misled by one particular case.
A number of very common order of magnitude functions will come up over and over as you study algorithms. These are shown in Table 1. In order to decide which of these functions is the dominant part of any T(n) function, we must see how they compare with one another as n gets large.
f(n) | Name |
---|---|
1 | Constant |
logn | Logarithmic |
n | Linear |
nlogn | Log Linear |
n2 | Quadratic |
n3 | Cubic |
2n | Exponential |
Figure 1 shows graphs of the common functions from Table 1. Notice that when n is small, the functions are not very well defined with respect to one another. It is hard to tell which is dominant. However, as n grows, there is a definite relationship and it is easy to see how they compare with one another.
As a final example, suppose that we have the fragment of Python code shown in Listing 2. Although this program does not really do anything, it is instructive to see how we can take actual code and analyze performance.
Listing 2
a=5
b=6
c=10
for i in range(n):
for j in range(n):
x = i * i
y = j * j
z = i * j
for k in range(n):
w = a*k + 45
v = b*b
d = 33
The number of assignment operations is the sum of four terms. The first term is the constant 3, representing the three assignment statements at the start of the fragment. The second term is 3n2, since there are three statements that are performed n2 times due to the nested iteration. The third term is 2n, two statements iterated n times. Finally, the fourth term is the constant 1, representing the final assignment statement. This gives us T(n)=3+3n2+2n+1=3n2+2n+4. By looking at the exponents, we can easily see that the n2 term will be dominant and therefore this fragment of code is O(n2). Note that all of the other terms as well as the coefficient on the dominant term can be ignored as n grows larger.
Figure 2 shows a few of the common Big-O functions as they compare with the T(n) function discussed above. Note that T(n) is initially larger than the cubic function. However, as n grows, the cubic function quickly overtakes T(n). It is easy to see that T(n) then follows the quadratic function as ncontinues to grow.
Self Check
Write two Python functions to find the minimum number in a list. The first function should compare each number to every other number on the list. O(n2). The second function should be linear O(n).
An Anagram Detection Example
A good example problem for showing algorithms with different orders of magnitude is the classic anagram detection problem for strings. One string is an anagram of another if the second is simply a rearrangement of the first. For example,
'heart'
and 'earth'
are anagrams. The strings'python'
and 'typhon'
are anagrams as well. For the sake of simplicity, we will assume that the two strings in question are of equal length and that they are made up of symbols from the set of 26 lowercase alphabetic characters. Our goal is to write a boolean function that will take two strings and return whether they are anagrams.Solution 1: Checking Off
Our first solution to the anagram problem will check to see that each character in the first string actually occurs in the second. If it is possible to “checkoff” each character, then the two strings must be anagrams. Checking off a character will be accomplished by replacing it with the special Python value
None
. However, since strings in Python are immutable, the first step in the process will be to convert the second string to a list. Each character from the first string can be checked against the characters in the list and if found, checked off by replacement. ActiveCode 4 shows this function.
1
def anagramSolution1(s1,s2):
2
alist = list(s2)
3
4
pos1 = 0
5
stillOK = True
6
7
while pos1 < len(s1) and stillOK:
8
pos2 = 0
9
found = False
10
while pos2 < len(alist) and not found:
11
if s1[pos1] == alist[pos2]:
12
found = True
13
else:
14
pos2 = pos2 + 1
15
16
if found:
17
alist[pos2] = None
18
else:
19
stillOK = False
20
21
pos1 = pos1 + 1
22
23
return stillOK
24
25
print(anagramSolution1('abcd','dcba'))
26
To analyze this algorithm, we need to note that each of the n characters in
s1
will cause an iteration through up to n characters in the list from s2
. Each of the n positions in the list will be visited once to match a character from s1
. The number of visits then becomes the sum of the integers from 1 to n. We stated earlier that this can be written as
n∑i=1i=n(n+1)2=12n2+12n
As n gets large, the n2 term will dominate the n term and the 12 can be ignored. Therefore, this solution is O(n2).
Solution 2: Sort and Compare
Another solution to the anagram problem will make use of the fact that even though
s1
and s2
are different, they are anagrams only if they consist of exactly the same characters. So, if we begin by sorting each string alphabetically, from a to z, we will end up with the same string if the original two strings are anagrams. ActiveCode 5 shows this solution. Again, in Python we can use the built-in sort
method on lists by simply converting each string to a list at the start.
1
def anagramSolution2(s1,s2):
2
alist1 = list(s1)
3
alist2 = list(s2)
4
5
alist1.sort()
6
alist2.sort()
7
8
pos = 0
9
matches = True
10
11
while pos < len(s1) and matches:
12
if alist1[pos]==alist2[pos]:
13
pos = pos + 1
14
else:
15
matches = False
16
17
return matches
18
19
print(anagramSolution2('abcde','edcba'))
20
At first glance you may be tempted to think that this algorithm is O(n), since there is one simple iteration to compare the n characters after the sorting process. However, the two calls to the Python
sort
method are not without their own cost. As we will see in a later chapter, sorting is typically either O(n2) or O(nlogn), so the sorting operations dominate the iteration. In the end, this algorithm will have the same order of magnitude as that of the sorting process.Solution 3: Brute Force
A brute force technique for solving a problem typically tries to exhaust all possibilities. For the anagram detection problem, we can simply generate a list of all possible strings using the characters from
s1
and then see if s2
occurs. However, there is a difficulty with this approach. When generating all possible strings from s1
, there are n possible first characters, n−1 possible characters for the second position, n−2 for the third, and so on. The total number of candidate strings is n∗(n−1)∗(n−2)∗...∗3∗2∗1, which is n!. Although some of the strings may be duplicates, the program cannot know this ahead of time and so it will still generate n! different strings.
It turns out that n! grows even faster than 2n as n gets large. In fact, if
s1
were 20 characters long, there would be 20!=2,432,902,008,176,640,000 possible candidate strings. If we processed one possibility every second, it would still take us 77,146,816,596 years to go through the entire list. This is probably not going to be a good solution.Solution 4: Count and Compare
Our final solution to the anagram problem takes advantage of the fact that any two anagrams will have the same number of a’s, the same number of b’s, the same number of c’s, and so on. In order to decide whether two strings are anagrams, we will first count the number of times each character occurs. Since there are 26 possible characters, we can use a list of 26 counters, one for each possible character. Each time we see a particular character, we will increment the counter at that position. In the end, if the two lists of counters are identical, the strings must be anagrams.ActiveCode 6 shows this solution.
1
def anagramSolution4(s1,s2):
2
c1 = [0]*26
3
c2 = [0]*26
4
5
for i in range(len(s1)):
6
pos = ord(s1[i])-ord('a')
7
c1[pos] = c1[pos] + 1
8
9
for i in range(len(s2)):
10
pos = ord(s2[i])-ord('a')
11
c2[pos] = c2[pos] + 1
12
13
j = 0
14
stillOK = True
15
while j<26 and stillOK:
16
if c1[j]==c2[j]:
17
j = j + 1
18
else:
19
stillOK = False
20
21
return stillOK
22
23
print(anagramSolution4('apple','pleap'))
24
Again, the solution has a number of iterations. However, unlike the first solution, none of them are nested. The first two iterations used to count the characters are both based on n. The third iteration, comparing the two lists of counts, always takes 26 steps since there are 26 possible characters in the strings. Adding it all up gives us T(n)=2n+26 steps. That is O(n). We have found a linear order of magnitude algorithm for solving this problem.
Before leaving this example, we need to say something about space requirements. Although the last solution was able to run in linear time, it could only do so by using additional storage to keep the two lists of character counts. In other words, this algorithm sacrificed space in order to gain time.
This is a common occurrence. On many occasions you will need to make decisions between time and space trade-offs. In this case, the amount of extra space is not significant. However, if the underlying alphabet had millions of characters, there would be more concern. As a computer scientist, when given a choice of algorithms, it will be up to you to determine the best use of computing resources given a particular problem.
Self Check
Q-1: Given the following code fragment, what is its Big-O running time?
test = 0
for i in range(n):
for j in range(n):
test = test + i * j
Q-2: Given the following code fragment what is its Big-O running time?
test = 0
for i in range(n):
test = test + 1
for j in range(n):
test = test - 1
Q-3: Given the following code fragment what is its Big-O running time?
i = n
while i > 0:
k = 2 + 2
i = i // 2
- Get link
- Other Apps
Comments
Post a Comment