Algorithm and Complexity:
An Algorithm is a well-defined list
of steps for solving a particular problem.
Two major measures of the efficiency
of an algorithm -
1.
Time
[measured by counting the number of key operations]
2.
Space
[measured by counting the maximum of memory needed by the algorithm]
The complexity of an algorithm is the
function f(n) which measures the time and/or space used by an algorithm in
terms of the input size n.
A file with n records -
For linear search, the average number
of comparison is n/2. So, complexity, C(n) = n/2
For binary search, the average number
of comparison is log2n. So, complexity, C(n) = log2n
Problem:
Suppose, a data set S contains n
elements,
Compare the running time T1
of the linear search algorithm with the running time T2 of the
binary search algorithm when, (i) n=1000 and (ii) n = 10000
Mathematical notation and function:
Floor function: [3.4] = 3, [-8.5] =
-9
Ceiling Function: [3.4] = 4, [-8.5] =
-8
Modulus Arithmetic: 25 (mod 7) = 4,
-4 (mod 6) = 2, 5 (mod 5) = 0 or 5
Using
'clock' arithmetic or modulo 12, 6+9=3, 7X5=11, 1-5=8
Integer Function: INT(3.4)=3,
INT(-8.5)=-8.5
Absolute Function: [7]=7, [-15]=15
# Write an algorithm to find the location (LOC) and the value (MAX) of
the largest element of N number of DATA.
Algorithm: (Use repeat-while)
1.
[Initialize]
Set K:=1, LOC:=1 and MAX:=DATA[1].
2.
Repeat
Steps 3 and 4 while K ≤ N:
3.
If
MAX < DATA[K], then:
Set LOC:=K and MAX:=DATA[K].
[End
of If Structure]
4.
Set
K:=K+1.
5.
Write:
LOC, MAX.
6.
Exit
Rate of Growth (Big O notation)
For linear search, in worst case, C(n)=n and
in average case,
C(n)=1.(1/n)+2.(1/n)+...+n.(1/n) = (n+1)/2
The complexity of the average case of
an algorithm is much more complicated to analyze than that of the worst case.
g(n)
n
|
log n
|
n
|
n log n
|
n2
|
n3
|
2n
|
5
|
3
|
5
|
15
|
25
|
125
|
32
|
10
|
4
|
10
|
40
|
100
|
103
|
103
|
100
|
7
|
100
|
700
|
104
|
106
|
1030
|
1000
|
10
|
103
|
104
|
106
|
109
|
10300
|
** log2n grows slowly and
2n grows rapidly.
Complexity:
Linear search: O(n)
Binary search: O(log n)
Bubble sort: O(n2)
Merge sort: O(n log n)
|
0 comments:
Post a Comment