The Note based on Data Structures and Algorithm Analysis in C,CHAPTER 2: ALGORIT

The Note based on Data Structures and Algorithm Analysis in C

CHAPTER 2: ALGORITHM ANALYSIS

1.1.Intro

Definition:

An algorithm is a clearly specified set of simple instructions to be followed to solve a problem.

Main issues:

(1). How to estimate the time required for a program.

(2). How to reduce the running time of a program from days or years to fractions of a second.

(3). The results of careless use of recursion.

(4). Very efficient algorithms to raise a number to a power and to compute the greatest common divisor of two numbers.

2.1. Mathematical Background

Throughout the book we will use the following four definitions:

DEFINITION: T(n) = O(f(n)) if there are constants c and n0 such that T(n) ≤ cf (n) when n ≥ n0.

DEFINITION: T(n) = Ω(g(n)) if there are constants c and n0 such that T(n) ≥cg(n) when n ≥ n0.

DEFINITION: T(n) = Θ(h(n)) if and only if T(n) = O(h(n)) and T(n) = Ω(h(n)).

DEFINITION: T(n) = o(p(n)) if T(n) = O(p(n)) and T(n)≠ Θ(p(n)).

// The last definition, T(n) = o(p(n)), says that the growth rate of T(n) is less than (<) the growth rate of p(n). This is different from Big-Oh, because Big-Oh allows the possibility that the growth rates are the same.

The idea of these definitions is to establish a relative order among functions. We compare their relative rates of growth. When we apply this to the analysis of algorithms, we shall see why this is the important measure.

To prove that some function T(n) = O(f(n)), we usually do not apply these definitions formally but instead use a repertoire of known results.

When we say that T(n) = O(f(n)), we are guaranteeing that the function T(n) grows at a rate no faster than f(n); thus f(n) is an upper bound on T(n). Since this implies that f(n) = Ω(T(n)), we say that T(n) is a lower bound on f(n).

Some Important Conclusions:

(1). RULE 1: If T1(n) = O(f(n)) and T2(n) = O(g(n)), then

(a) T1(n) + T2(n) = max (O(f(n)), O(g(n))).

(b) T1(n) * T2(n) = O(f(n) * g(n)).

(2). RULE 2: If T(x) is a polynomial of degree n, then T(x) = Θ (xk).

(3). RULE 3: (logN)k= O(n) for any constant k. This tells us that logarithms grow very slowly.

Do not say T(n) = O(2n2) or T(n) = O(n2 + n). In both cases, the correct form is T(n) = O(n2). (Most Simplified)

Typical growth rates:

* The L'Hôpital's rule: The limit=limn→∞fn/limn→∞gn = limn→∞fn' / limn→∞fn'

The limit can give us their relative rates of growth.

The limit is 0: This means that f(n) = o(g(n)).

The limit is c ≠ 0: This means that f(n) = Θ(g(n)).

The limit is ∞ : This means that g(n) = o(f(n)).

The limit oscillates: There is no relation (this will not happen in our context).

Using this method almost always amounts to overkill.

2.2. Model

Our model is basically a normal computer, in which instructions are executed sequentially. We also assume infinite memory.

The advantages: Obviously, in real life, not all operations take exactly the same time. faster. Also, by assuming infinite memory, we never worry about page faulting, which can be a real problem, especially for efficient algorithms. This can be a major problem in many applications.

2.3. What to Analyze?

The standard for a good algorithm: We remark that generally the quantity required is the worst-case time, unless otherwise specified.

EXAMPLE: THE MAXIMUM SUBSEQUENCE SUM PROBLEM.

Executing time:

It dramatically illustrates how useless inefficient algorithms are for even moderately large amounts of input.

2.4. Running Time Calculations

If two programs are expected to take similar times, probably the best way to decide which is faster is to code them both up and run them!

To simplify the analysis, we will adopt the convention that there are no particular units of time. Thus, we throw away leading constants. We will also throw away low-order terms, so what we are essentially doing is computing a Big-Oh running time. Since Big-Oh is an upper bound, we must be careful to never underestimate the running time of the program.

2.4.1. Running Time Calculations

/****************************************************************

* A SUM FUNCTION.

* A simple program fragment to calculate i^3, i = [1, N].

* int i, int PartialSum

******************************************************************/

sum(int N){

int i, PartialSum;//declear variables don't occupy any time unit

PartialSum = 0;//1 time unit

for(i = 1, i<= N, i++){//2N + 2 time units = Initialize(1 time unit) + All test(N + 1 time units) + "i++"(N time units)

PartialSum += i * i * i;//(4 time units -> 2 times of multiplication, 1 addition, 1 assignment) * N Times

}

return PartialSum;//1 time unit

}

// (6N + 4) time units in total -> O(N)

2.4.2. General Rules

RULE 1-FOR LOOPS:

The running time of a for loop is at most the running time of the statements inside the for loop (including tests) times the number of iterations.

RULE 2- NESTED FOR LOOPS:

//Analyze these inside out. The total running time

//of a statement inside a group of nested for loops is the running

//time of the statement multiplied by the product of

//the sizes of all the for loops.

//As an example, the following program fragment is O(N^2):

for(i = 0; i < N； i++)

for(j = 0; j < N; j++)

k++;//total running time = 1 * N * N

RULE 3-CONSECUTIVE STATEMENTS:

for(i = 0; i < N; i++)

A[i] = 0; //O(N)

for(i = 0; i < N;)

for(j = 0; j < N; j++)

A[i] += A[j] + i + j;//O(N^2)

//total running time = the addition of partial running times

//total running time = max(O(N^2), O(N)) = O(N^2)

RULE 4-lF/ELSE:

//fragment

if(Condition)

S1;

else

S2;

//the running time of an if/else statement is never more than the running time of the test

//plus the larger of the running times of S1 and S2.

//The basic strategy of analyzing from the inside (or deepest part) out works.

//If there are function calls, obviously these must be analyzed first.

//If there are recursive procedures, there are several options.

//If the recursion is really just a thinly veiled for loop, the analysis is usually trivial.

long int

Factorial(int n)

{

if(N <= 1)

return 1;

else

return N * Factorial(N - 1);//recursion -> for loop! --> O(N)

}

//This example is really a poor use of recursion. When recursion is properly used,

//it is difficult to convert the recursion //into a simple loop structure.

long int

Fib(int N){

if(N <= 1)

return 1;

else

return Fib(N - 1) + Fib(N - 2);

}

/**************************************************************

*Analysis:

*When N = 0 || N = 1: T is a constant -> O(c).

*When N > 2: T（N) = T(N - 1) + T(N - 2) + 2. // "2" means " if(N <= 1)" + "return Fib(N - 1) + Fib(N - 2);"

*For Fib(N) = Fib(N - 1) + Fib(N - 2) -> T(N) >= Fib(N).

***************************************************************/

The fragment executes as an exponential function. (The worst case)

2.4.3. Solutions for the Maximum Subsequence Sum Problem

Four Algorithms：

//Solutions for the Maximum Subsequence Sum Problem

//Algorithm 1: Method of Exhaustion -> f(N) = O(N^3)

int

MaxSubsequenceSum(const int A[ ]， int N){

int ThisSum, MaxSum, i, j, k;

MaxSum = 0;

for(i = 0; i < N; i++)//T = N -> O(N)

for(j = i; j < N; j++){//T = N - i -> O(N)

ThisSum = 0;

for(k = i; k <= j; k++)//T = j - i + 1 -> O(N)

ThisSum += A[k]; //T = 1 --> Contained by three nested "for" loops. T = O(1*N*N*N)

if(ThisSum > MaxSum)//T = O(2*N^2)

MaxSum = ThisSum;

}

return MaxSum;

}

//Alogorithm 2: Method of Exhaustion - Improved -> f(N) = O(N^2)

int

MaxSubsequenceSum(const int A[ ], int N){

int ThisSum, MaxSum, i, j;

MaxSum = 0;

for(i = 0; i < N; i++){//T = N -> O(N)

ThisSum = 0;

for(j = i; j < N; j++){//T = N - i -> O(N)

ThisSum += A[j];

if(ThisSum > MaxSum)

MaxSum = ThisSum;

}

}

return MaxSum;

}

//Algorithm 3: Recursion - Devide and Conqure

static int

MaxSubSum(const A[ ], int left, int right){

int MaxLeftSum, MaxRightSum;

int MaxLeftBorderSum, MaxRightBorderSum;

int LeftBorderSum, RightBorderSum;

int Center, i;

if(Right == Left)//deal with the basic case

if(A[Left] > 0)

return A[Left];

else

return 0;//T(N) = O(1). ignore.

Center = (Left + Right) / 2;

MaxLeftSum = MaxSubSum(A, Left, Center);// excuting two times of recursion - devide a big puzzle into small pieces.

MaxRightSum = MaxSubSum(A, Center + 1, Right);//Solve the problem (size is 'N/2') -> T = 2T（N/2)

MaxLeftBorderSum = 0; //calculate the MaxSum in the left part.

LeftBorderSum = 0;//T(N) = O(1). ignore.

for(i = Center, i > Left, i--){

LeftBorderSum += A[i];

if(LeftBorderSum > MaxLeftBorderSum)

MaxLeftBorderSum = LeftBorderSum;

}

//These two 'for' loops -> from A[0] -> A[N - 1] --> O(N)

MaxRightBorderSum = 0;{//calculate the MaxSum in the right part.

RightBorderSum = 0;//T(N) = O(1). ignore.

for(i = Center + 1, i < Right, i++)

RightBorderSum += A[i];

if(RightBorderSum > MaxRightBorderSum)

MaxRightBorderSum = RightBorderSum;

}

return max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);//T(N) = O(1). ignore.

// return the maximum of these three possible(to be the maximun one) value.(pseudoroutine)

}

int

int MaxSubsequenceSum(const int A[ ], int N){

return MaxSubSum(A, 0, N - 1);

}

/* T(1) = 1;

T(N) = 2T(N/2) + O(N);*/

//Algorithm 4 On-Line algorithm T(N) = O(N)

int

MaxSubsequenceSum( const int A[ ], int N){

int ThisSum, MaxSum, j;

ThisSum = MaxSum = 0;

for(j = 0; j < N; j++){

ThisSum += A[j];

if(ThisSum > MaxSum)

MaxSum = ThisSum;

else if(ThisSum < 0)

ThisSum = 0;

}

return MaxSum;

}

2.4.4 Logarithms in the Running Time

Definition: Besides divide-and-conquer algorithms, the most frequent appearance of logarithms centers around the following general rule.

An algorithm is O(logN) if it takes constant (O(1)) time to cut the problem size by a fraction (which is usually 1/2). On the other hand, if constant time is required to merely reduce the problem by a constant amount (such as to make the problem smaller by 1), then the algorithm is O(N).

It should be obvious that only special kinds of problems can be O(logN). For instance, if the input is a list of N numbers, an algorithm must take (N) merely to read the input in. Thus, when we talk about O(logN) algorithms for these kinds of problems, we usually presume that the input is preread.

int

BinarySearch(const ElementType A[ ], ElementType X, int N){

int Low, Mid, High;

Low = 0;

High = N - 1;

while(Low <= High){

/***************************************************

*begin at "High - Low = N - 1" end with "High - Low >= -1"

*each time at least the value of "High - Low" -> 1/2 * original value

*loop maximum time = [log(N - 1)] +2 -> O(logN)

***************************************************/

Mid = (Low + High) / 2;

if(A[Mid] < X)

Low = Mid + 1;//O(1)

else

if(A[Mid] > X)

High = Mid -1;//O(1)

else

return Mid;//O(1)

}

return NotFound;

}

//2.Euclidean algorithm

//in the case -> 'M >= N'

unsigned int

Gcd(unsigned int M, unsigned int N){

unsigned int Rem;

while(N > 0)

{

Rem = M % N;

M = N;

N = Rem;

}

return M;

}// T(N) = 2log(N) = O(logN)

/***********************************************************************************

*since we see that the remainder went from 399 to only 393 in the example. Indeed, the

*remainder does not decrease by a constant factor in one iteration. However, we can prove

*that after two iterations, the remainder is at most half of its original value.

-->THEOREM 2.1: If M > N, then M mod N < M/2.

**************************************************************************************/

//3.Exponentiation T(N) = O(logN)

long int

Pow(long int X, unsigned int N){

if(N == 0)

return 1;

if(N == 1)

return X;

if(IsEven(N))//when N is even, X^N = X^(N/2) * X^(N/2).

return Pow(X * X, N / 2);

else//when N is odd, X^N = X^(N-1/2) * X^(N-1/2) * X.

return Pow(X * X, N / 2) * X;//return Pow(X, N - 1) * X

}

Reference：

[1] Data Structures and Algorithm Analysis in C. Mark Allen Weiss. [M].Addison Wesley:Britain,1996-09-19:51-76.