Algorithms
An algorithm is a sequence of computational steps that transform some input into some output.
It is a tool for solving a well-defined computational problem.
Examples of such problems --- searching, sorting
Searching
Linear Search Algorithm
-- looks sequentially at each element of a given collection of elements until we either come to the end of the sequence of elements
or find an item that equals to X (the element that we are searching for).
public int linearSearch(int[] A, int x)
{ constant time to execute times to execute
for (int i=0; i<A.length, i++) C1 n+1 times
{
if (A[i] = = x ) C2 n times
return i; C3 0 or 1 time
}
return (–1); // returns –1 when the element is not found C4 1 or 0 time
}
The complexity of Linear Search Algorithm is order of n (O(n)), where n is the number of elements.
The running time T(n) is bounded by C1*(n+1) + C2*n + C3 + C4 = (C1+C2)*n + (C1+C3+C4), it is a linear function of n.
O-notation -- upper bound
The (worst case) running time of the linear search can be expressed as a function of n, where n is an input size.
T(n) = c1 * n + c2
where c1 and c2 are positive constants.
Intuitively, we can see that when n, input size, gets larger, the time that takes to execute the linear search grows.
(T(n) grows proportionally to n. ) And when n gets very large, constant c2 has a very small effect on the running time.
We say that the complexity of the linear search is O(n),
but here is a formal definition of O (pronounced as “big-Oh”) notation.
Definition of O-notation:
If there exist positive constants a and c such that
(Run time) a=c1+c2+1 g(n)=(n)
T(n) <= a*g(n) for all n larger than c
Then we say that T(n) = O(g(n)). This means that g(n) is an upper bound of T(n).
For the linear search, g(n) = n. Note that there is more than one such function g(n).
For instance it is correct to say that:
T(n) = O(n2 )
for the running time of the linear search though this is not a tight upper bound.
n
a*g(n)
T(n)
c
When n gets larger (greater than c),
we can find a positive constant a
such that T(n) <= a*g(n)
Ω-notation (Omega-notation) – lower bound
Similarly, we can define a lower bound for each running time.
If there exist positive constants b and c such that
T(n) >= b* g(n) for all n larger than c
Then we say that T(n) = Ω ( g(n) ) where g is a function of n.
Thus g(n) is a lower bound of the running time T(n).
Θ-notation (Theta-notation)
If T(n) = O( g(n) ) and T(n) = Ω ( g(n) ),
Then we say that:
T(n) = Θ ( g(n) )
Thus the function g represents a tight bound for T(n).
Example:
Suppose that T(n) = n2 + 5n -3
Then T(n) = Θ (n2 ), but it is NOT correct to say T(n) = Θ (n3 ) or T(n) = Θ (n ).
Binary Search Algorithm
-It is used to look up a word in a dictionary or a name in a phone book.
-It uses Divide and Conquer approach.
-A list needs to be sorted before a binary search (pre-condition).
Example: Search for x = 11
-5 –2 7 9
9 11 12 20 31 x > 9, so x is in right half segment.
11 12
12 20 31 x < 12, so x is in left quarter segment
11 12 x == 11. We found x.
The complexity of Binary Search Algorithm is order of log n
where n is the number of elements to search from
Binary Search Using iterative method
If x is found, it returns the index of the element,
otherwise it returns –1.
public static int binIter(int[] num, int x)
{
int n = num.length;
if (x>num[n-1] || x<num[0])
return -1; // x is not found
int i = 0;
int j = n-1;
int k;
while (i<j)
{
k = (int) Math.floor((i+j)/(2.0));
if (x<=num[k])
j = k;
else
i = k+1;
}
if (num[i] == x)
return i; // x is found
else
return -1; // x is not found
}
Sorting
--the process of arranging a list of items into a particular order.
Selection Sort Algorithm
It sorts a list of values by successively putting particular values (the smallest value among unsorted values) in their final sorted position.
Example:
1 9 6 1 2 Find the smallest (1), and exchange so that the smallest will be at the left most
1 9 6 3 2 Find the second smallest (2), and exchange so that the 2nd smallest will be at the 2nd left most
1 2 6 3 9 Find the third smallest (3), and exchange
1 2 3 6 9 Find the fourth smallest. The fourth smallest is already in the right position, no exchange.
1 2 3 6 9
The complexity of the selection sort algorithm is order of n2
//-----------------------------------------------------------------
// Sorts the specified array of integers using the selection
// sort algorithm.
//-----------------------------------------------------------------
public static void selectionSort (int[] numbers)
{
int min, temp;
for (int index = 0; index < numbers.length-1; index++)
{
min = index;
for (int scan = index+1; scan < numbers.length; scan++)
if (numbers[scan] < numbers[min])
min = scan;
// Swap the values
temp = numbers[min];
numbers[min] = numbers[index];
numbers[index] = temp;
}
}
This line compares two values.
How many comparison are done in this
algorithm? Let n be the length of the array.
When index = 0,
scan goes from 1 to n-1, thus n-1 iterations.
When index = 1,
scan goes from 2 to n-1, thus n-2 iterations.
…..
When index = n-2,
scan foes from n-1 to n-1, 1 iteration.
The total number of iterations is:
(n-1)+(n-2)+…1 = (n-1)n/2
=(1/2)n2-(1/2)n
We look at the fastest growing term: n2
Thus we say:
The complexity of the selection sort
algorithm is order of n2
Powered by TCPDF (www.tcpdf.org)
