Transcript Chapter 1 Algorithm Analysis

Hail
of
University
ICS 202

Data Structures and Algorithms

Instructor : Da’ad Ahmad Albalawneh
1
Outline
University
of
Hail
1. Introduction
2. A Detailed Model of the Computer
•
The Basic Axioms
•
Example 1: Arithmetic Series Summation
•
Array Subscribing Operations
•
Example2: Horner’s Rule
•
Analyzing Recursive Methods
•
Example 3: Finding the Largest Element of an Array
•
Average Running Times
•
About Harmonic Numbers
•
Best-Case and Worst-Case Running Times
•
The Last Axiom
3. A Simplified Model of the Computer
•
Example 1: Geometric Series Summation
•
About Geometric Series Summation
•
Example 2: Computing Powers
2
1. Introduction
University
of
Hail
• What is an Algorithm?
•
“A step-by-step procedure for accomplishing some end”
•
Can be written in English, or using an appropriate mathematical formalism –
programming language
• Why do we analyze an algorithm and what can we analyze?
•
To learn more about the algorithm (some specifications)
•
To draw conclusions about how the implementation will perform
•
We can analyze
•
The running time of a program as a function of its inputs
•
The total or maximum memory space needed for program data
•
The total size of the program code
•
The complexity of the program
•
The robustness (powerful) of the program (how wll does it deal with unexpected inputs)
3
•
The algorithm itself
of
• Factors affecting the running time of a program
•
The input data
University
Hail
1. Introduction
•
The computer system used to run the program
•
The hardware (Processor, memory available, disk available, …)
•
The programming language
•
The language compiler
•
The computer operating system software
4
2. A Detailed Model of the Computer
• The model is independent of the hardware and system software
• Modeling the execution of a JAVA program on the “Java Virtual Machine”
University
of
Hail
• Detailed model of the running time performance of JAVA programs
Java system
Java Virtual
Machine
Java
Program
Java Compiler
Java
bytecode
Java bytecode
interpreter
Physical Machine
Machine
code
Hardware
5
2. A Detailed Model of the Computer: The Basic Axioms
University
of
Hail
• Axiom 1
The time required to fetch an operand from memory is a constant,  fetch and the time
required to store a result in memory is a constant,
y = x; has running time
 fetch   store
y = 1; has running time
 fetch   store
 store
The two statements have the same running time because the
constant 1 needs to be stored in memory
6
2. A Detailed Model of the Computer: The Basic Axioms
Hail
respectively.
University
The times required to perform elementary operations, such as addition, subtraction,
of
• Axiom 2
multiplication, division, and comparison, are all constants. These times are denoted by:
  ,  ,  ,  , and  
 All of the simple operations can be accomplished in a fixed amount of time
 The number of bits used to represent a value must be fixed
 In Java, the number of bits range from 8 (byte) to 64 (long and double)
7
2. A Detailed Model of the Computer: The Basic Axioms
By applying the axiom 1 and 2, the running time for the statement y = y + 1; is
2 fetch      store
University
of
Hail
Example:
Because we need to fetch two operands, y and 1, add them, and, store the result
back in y
y+ = 1;
++y;
y++;
Have the same running time as y = y + 1;
8
2. A Detailed Model of the Computer: The Basic Axioms
The time required to call a method is a constant,  call and the time required to return
from a method is a constant,
 return
University
of
Hail
• Axiom 3
When a method is called:
• The returned address must be saved
• Any partially completed computations must also be saved
• A new execution context (stack frame, …) must be allocated
9
2. A Detailed Model of the Computer: The Basic Axioms
The time required to pass an argument to method is the same as the time required to
store a value in memory
 store
University
of
Hail
• Axiom 4
Example:
y = f(x); has a running time:
Where
 fetch  2 store   call  T f ( x )
T f ( x )is the running time of method f for input x.
We need one store time to pass the parameter x to f and a store time to assign the
result to y.
10
2. A Detailed Model of the Computer: Example 1: Arithmetic Series Summation
n
i
i 1
public class Example1
{
of
1
2
3
public static int sum (int n)
University
Hail
Analyze the running time of a program to compute
4
{
5
int result = 0;
6
for(int i = 1; i <= n; ++i)
result += i;
7
return result;
8
}
9
10
}
11
University
of
Hail
2. A Detailed Model of the Computer: Example 1: Arithmetic Series Summation
Statement
Time
Code
5
 fetch   store
result = 0
6a
 fetch   store
i=1
6b
(2 fetch    )  (n  1)
i <= n
6c
(2 fetch      store)  n
++i
7
(2 fetch      store)  n
result += i
8
 fetch   return
return result
T (n)  n  (6 fetch  2 store     2  )  (5 fetch  2 store      return )
12
2. A Detailed Model of the Computer: Array Subscribing Operations
University
of
Hail
• The elements of a one-dimensional array are stored in consecutive (sequential)
memory locations
• We need to know only the address of the first element of the array to determine
the address of any other element
• Axiom 5
The time required for the address calculation implied by an array subscribing
operation, for example, a[i], is a constant,  [.] This time does not include the time to
compute the subscript expression, nor does it include the time to access (i.e., fetch or
store) the array element.
13
University
of
Hail
2. A Detailed Model of the Computer: Array Subscribing Operations
Example:
y = a [i]; has a running time:
3 fetch   [.]   store
Three operand fetches:
• The first to fetch a (the base address of the array)
• The second to fetch i (the index into the array)
• The third the fetch array element a[i]
14
2. A Detailed Model of the Computer: Example 3: Finding the largest Element of an Array
University
of
Hail
Analyze the running time of a program to find the largest element of an array of
n non-negative integers,
a0 , a1 ,..., an 1 max ai
0i  n
1
public class Example
2
{
3
public static int findMaximum (int [ ] a)
4
{
5
int result = a [0];
6
for(int i = 1; i <a.length; ++i)
if(a[i]) > result)
7
result = a[i];
8
return result;
9
}
10
11
}
15
University
of
Hail
2. A Detailed Model of the Computer: Example 3: Finding the largest Element of an Array
Statement
Time
Code
5
3 fetch   [.]   store
6a
 fetch   store
6b
(2 fetch    )  n
6c
(2 fetch      store )  (n  1)
7
(4 fetch   [.]    )  (n  1)
8
(3 fetch   [.]   store)  ?
result = a[i]
9
 fetch   return
return result
result = a [0]
i=1
i < a.length
++i
if(a[i] > result)
16
 The worst case scenario occurs when line 8 is executed in every iteration of the
loop.
 The input array is ordered from smallest to largest
University
of
Hail
2. A Detailed Model of the Computer: Best-Case and Worst-Case Running Times
17
 The best case scenario occurs when line 8 is never executed.
 The input array is ordered from largest to smallest
University
of
Hail
2. A Detailed Model of the Computer: Best-Case and Worst-Case Running Times
18
2. A Detailed Model of the Computer: The Last Axiom
University
of
Hail
• Axiom 6
The time required to create a new object instance using the new operator is a
constant,
 new
. This time does not include any time taken to initialize the object
instance.
Example:
Integer ref = new Integer (0); has a running time:
 new   fetch  2 store   call   ( Integer)
Where
 ( Integer)is the running time of the Integer constructor
19
Hail
• All the arbitrary timing parameters of the detailed model are eliminated
University
• The performance analysis is easy to do but less accurate
of
3. A Simplified Model of the Computer
• All timing parameters are expressed in units of clock cycles , T =1
• To determine the running time of a program, we simply count the total number of
cycles taken
20
3. A Simplified Model of the Computer: Example 2: Geometric Series Summation
n
i
x
Analyze the running time of a program to compute  using Horner’s rule
Hail
i 0
of
1
2
University
3
4
5
6
7
8
9
10
public class Example2
{
public static int geometricsum (int x, int n)
{
int sum = 0;
for(int i = 0; i <= n; ++i)
sum = sum * x +1;
return sum;
}
}
21
Time
Hail
5
2
sum = 0
6a
2
i=0
6b
3(n  2)
i <=n
6c
4( n  1)
++i
7
6( n  1)
sum = sum*x + 1
8
2
University
Statement
of
3. A Simplified Model of the Computer: Example 2: Geometric Series Summation
Code
return sum
Total  13n  22
22
3. A Simplified Model of the Computer: About Geometric Series Summation
n
3
1, x, x , x ,... is a geometric series and the summation
sn   x i
i 0
Is called the geometric series summation
n 1
x
1
i
sn   x 
x 1
i 0
n
University
of
Hail
The series
2
23