Algorithm Making
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Algorithm Making as PDF for free.
More details
- Words: 1,067
- Pages: 24
Computer Programming II (TA C252, Lect 9_10)
Today’s Agenda
Efficiency & Complexity
Efficiency in Programming
Good Programming Practices
Avoid redundant computation Avoid unnecessary array references Inefficiency due to late termination Early detection of desired output conditions
Issues Order of Complexity
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
2
Avoid redundant computations x=0;a=5;b=2;
x=0;a=5;b=2; for(i=0;i
Friday, September 4, 2009
const1=a*a*a+c; const2=b*b; for(i=0;i
Biju K Raveendran@BITS Pilani.
3
Avoid unnecessary array references p=0; for(i=1;ia[p]) p=i; } max=a[p];
Friday, September 4, 2009
p=0; max=a[0]; for(i=1;imax) { p=i; max=a[i]; } } Biju K Raveendran@BITS Pilani.
4
Inefficiency due to late termination for (i=0;i
Friday, September 4, 2009
for (i=0;ix) return NOT FOUND; i++; } return NOT FOUND;
Biju K Raveendran@BITS Pilani.
5
Early detection of desired output sorted=0; condition i=0; while ( ( i < N ) && ( sorted = = 0) ) { j=0; sorted=1; while ( j < (N – i – 1) ) { if(a[j]> a[(j+1)]) { temp=a[j]; a[j]=a[(j+1)]; a[(j+1)]=temp; sorted=0; } j++; } i++; }
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
6
What is Efficiency ?
Efficiency – Design & Implementation issue. Resources
CPU Time Storage
Resource Usage
Measured proportional to (input) size
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
7
Design Level Measurement
Machine-independent measurement needed
Often referred to as “algorithmic complexity” Individual statement considered as “unit” time
Not applicable for function calls and loops
Individual variable considered as “unit” storage
Not applicable for arrays (or other collections)
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
8
Order of complexity [1]
Example 1 (Y and Z are input) X = 3 * Z; X = Y + X; // 2 units of time and 1 unit of storage
// Constant Unit of time and Constant Unit of storage
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
9
Order of complexity [2]
Example 2 (a and N are input) j = 0; while (j < N) do a[j] = a[j] * a[j]; b[j] = a[j] + j; j = j + 1; endwhile; // 3N + 1 units of time and N+1 units of storage // time units prop. to N and storage prop. to N
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
10
Order of complexity [3]
Example 2 (a and N are input) j = 0; while (j < N) do k = 0; while (k < N) do a[k] = a[j] + a[k]; k = k + 1; endwhile; b[j] = a[j] + j; j = j + 1; endwhile; // time prop. to N2 and storage prop. to N
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
11
Motivation for Order Notation log2N
N
N2
N3
2N
1
2
4
8
4
3.3
10
102
103
>103
6.6
100
104
106
>1025
9.9
1000
106
109
>10250
13.2
10000
108
1012
>102500
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
12
Motivation for Order Notation
Examples •
100 * log2N < N
•
70 * N + 3000 < N2 for N > 100 105 * N2 + 106 * N < 2N for N > 26
•
Friday, September 4, 2009
for N > 1000
Biju K Raveendran@BITS Pilani.
13
Order Notation Asymptotic Complexity g(n) is O(f(n)) if there is a constant c such that g(n) <= c(f(n)) i.e. limn∝ (g(n) / f(n)) = c and c<>0
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
14
Linear Search - Complexity function search(X, A, N) j = 0; while (j < N) if (A[j] == X) return j; j++; endwhile; return “Not_found”;
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
15
Linear Search - Complexity
Time Complexity: “if” statement introduces possibilties
Best-case: O(1) Worst case: O(N) Average case: ???
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
16
Linear Search - Complexity
Average case • •
•
Assume elements in A are randomly distributed. Then for N different cases, 1, 2, 3, … N are equally possible values of number of iterations. So expected value: (1 + 2 + … + N) / N
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
17
Linear Search - Complexity
Average case (Σi=0 to N I)/N = (N(N+1)/2 )/N = (N+1)/2 is O(N)
Space Complexity O(1)
i.e. constant space.
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
18
Binary Search Algorithm low = 0; high = N-1; while (low <= high) do mid = (low + high) /2; if (A[mid] = = x) return x; else if (A[mid] < x) low = mid +1; else high = mid – 1; endwhile; return Not_Found;
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
19
Binary Search - Complexity
Often not interested in best case. Worst case:
Loop executes until low <= high Size halved in each iteration N, N/2, N/4, … 1 How many steps ?
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
20
Binary Search - Complexity
Worst case:
K steps such that 2K = N i.e. log2N steps
is O(log(N))
Best case:
O(1)
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
21
Binary Search - Complexity
Average Case: 1 + 2 + 2 + 3 + 3 + 3 + 3 + … (upto logN steps) Sigma((i+1)*2i) for i = 0 to log2N Evaluates to O(log N) 1 element can be found with 1 comparison 2 elements 2 4 elements 3 Above Sum =sum over all possibilities
Space Complexity is O(1)
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
22
xy - Complexity
Assume y = 2k
k steps in the iteration. Complexity is O(k)
General case Sigma(log22k) for k = 1 to log2 y log (Product(2k)) for k =1 to log2y log(y)
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
23
Complexity Example: xy
Discuss if time permits
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
24
Today’s Agenda
Efficiency & Complexity
Efficiency in Programming
Good Programming Practices
Avoid redundant computation Avoid unnecessary array references Inefficiency due to late termination Early detection of desired output conditions
Issues Order of Complexity
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
2
Avoid redundant computations x=0;a=5;b=2;
x=0;a=5;b=2; for(i=0;i
Friday, September 4, 2009
const1=a*a*a+c; const2=b*b; for(i=0;i
Biju K Raveendran@BITS Pilani.
3
Avoid unnecessary array references p=0; for(i=1;i
Friday, September 4, 2009
p=0; max=a[0]; for(i=1;i
4
Inefficiency due to late termination for (i=0;i
Friday, September 4, 2009
for (i=0;i
Biju K Raveendran@BITS Pilani.
5
Early detection of desired output sorted=0; condition i=0; while ( ( i < N ) && ( sorted = = 0) ) { j=0; sorted=1; while ( j < (N – i – 1) ) { if(a[j]> a[(j+1)]) { temp=a[j]; a[j]=a[(j+1)]; a[(j+1)]=temp; sorted=0; } j++; } i++; }
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
6
What is Efficiency ?
Efficiency – Design & Implementation issue. Resources
CPU Time Storage
Resource Usage
Measured proportional to (input) size
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
7
Design Level Measurement
Machine-independent measurement needed
Often referred to as “algorithmic complexity” Individual statement considered as “unit” time
Not applicable for function calls and loops
Individual variable considered as “unit” storage
Not applicable for arrays (or other collections)
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
8
Order of complexity [1]
Example 1 (Y and Z are input) X = 3 * Z; X = Y + X; // 2 units of time and 1 unit of storage
// Constant Unit of time and Constant Unit of storage
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
9
Order of complexity [2]
Example 2 (a and N are input) j = 0; while (j < N) do a[j] = a[j] * a[j]; b[j] = a[j] + j; j = j + 1; endwhile; // 3N + 1 units of time and N+1 units of storage // time units prop. to N and storage prop. to N
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
10
Order of complexity [3]
Example 2 (a and N are input) j = 0; while (j < N) do k = 0; while (k < N) do a[k] = a[j] + a[k]; k = k + 1; endwhile; b[j] = a[j] + j; j = j + 1; endwhile; // time prop. to N2 and storage prop. to N
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
11
Motivation for Order Notation log2N
N
N2
N3
2N
1
2
4
8
4
3.3
10
102
103
>103
6.6
100
104
106
>1025
9.9
1000
106
109
>10250
13.2
10000
108
1012
>102500
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
12
Motivation for Order Notation
Examples •
100 * log2N < N
•
70 * N + 3000 < N2 for N > 100 105 * N2 + 106 * N < 2N for N > 26
•
Friday, September 4, 2009
for N > 1000
Biju K Raveendran@BITS Pilani.
13
Order Notation Asymptotic Complexity g(n) is O(f(n)) if there is a constant c such that g(n) <= c(f(n)) i.e. limn∝ (g(n) / f(n)) = c and c<>0
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
14
Linear Search - Complexity function search(X, A, N) j = 0; while (j < N) if (A[j] == X) return j; j++; endwhile; return “Not_found”;
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
15
Linear Search - Complexity
Time Complexity: “if” statement introduces possibilties
Best-case: O(1) Worst case: O(N) Average case: ???
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
16
Linear Search - Complexity
Average case • •
•
Assume elements in A are randomly distributed. Then for N different cases, 1, 2, 3, … N are equally possible values of number of iterations. So expected value: (1 + 2 + … + N) / N
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
17
Linear Search - Complexity
Average case (Σi=0 to N I)/N = (N(N+1)/2 )/N = (N+1)/2 is O(N)
Space Complexity O(1)
i.e. constant space.
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
18
Binary Search Algorithm low = 0; high = N-1; while (low <= high) do mid = (low + high) /2; if (A[mid] = = x) return x; else if (A[mid] < x) low = mid +1; else high = mid – 1; endwhile; return Not_Found;
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
19
Binary Search - Complexity
Often not interested in best case. Worst case:
Loop executes until low <= high Size halved in each iteration N, N/2, N/4, … 1 How many steps ?
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
20
Binary Search - Complexity
Worst case:
K steps such that 2K = N i.e. log2N steps
is O(log(N))
Best case:
O(1)
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
21
Binary Search - Complexity
Average Case: 1 + 2 + 2 + 3 + 3 + 3 + 3 + … (upto logN steps) Sigma((i+1)*2i) for i = 0 to log2N Evaluates to O(log N) 1 element can be found with 1 comparison 2 elements 2 4 elements 3 Above Sum =sum over all possibilities
Space Complexity is O(1)
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
22
xy - Complexity
Assume y = 2k
k steps in the iteration. Complexity is O(k)
General case Sigma(log22k) for k = 1 to log2 y log (Product(2k)) for k =1 to log2y log(y)
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
23
Complexity Example: xy
Discuss if time permits
Friday, September 4, 2009
Biju K Raveendran@BITS Pilani.
24
Related Documents
Algorithm Making
May 2020 9
Algorithm
October 2019 95
Algorithm
November 2019 83
Algorithm
May 2020 56
Algorithm
November 2019 82
Making
May 2020 14More Documents from "farhan sultan"
Graphs: Nitin Upadhyay
June 2020 5
Chapter 5
June 2020 10
Graphs Lect3
June 2020 8
Pspice Final
May 2020 4
Algorithm Making
May 2020 9