Transcript Introduction Data Structures & Algorithm

Introduction Data Structures &
Algorithm
Data Structures & Algorithm
Data Structures & Algorithm
• Algorithm: Outline, the essence of a
computational procedure, step-by-step
instructions
• Program: an implementation of an algorithm in
some programming language
• Data structure: Organization of data needed to
solve the problem
2012-2013
2
History
• Name: Persian mathematician Mohammed alKhowarizmi, in Latin became Algorismus
• First algorithm: Euclidean Algorithm, greatest
common divisor, 400-300 B.C.
• 19th century – Charles Babbage, Ada Lovelace.
• 20th century – Alan Turing, Alonzo Church, John von
Neumann
2012-2013
3
Algorithmic problem
Specification
of input
?
Specification
of output as
a function of
input
• Infinite number of input instances satisfying the specification. For
example:
• A sorted, non-decreasing sequence of natural numbers. The sequence is
of non-zero, finite length:
• 1, 20, 908, 909, 100000, 1000000000.
• 3.
2012-2013
4
Algorithmic Solution
Input instance,
adhering to
the
specification
Algorithm
Output
related to
the input as
required
• Algorithm describes actions on the input instance
• Infinitely many correct algorithms for the same algorithmic problem
2012-2013
5
What is a Good Algorithm?
• Efficiency:
• Running time
• Space used
• Efficiency as a function of input size:
• Number of data elements (numbers, points)
• A number of bits in an input number
2012-2013
6
Measuring the Running Time
• How should we measure the running time
of an algorithm?
• Approach 1: Experimental Study
• Write a program that implements the algorithm
• Run the program with data sets of varying size
and composition.
• Use a method like System.currentTimeMillis() to
get an accurate measure of the actual running
time.
t (ms)
60
50
40
30
20
10
0
2012-2013
n
50
100
7
Limitation Experimental Studies
• Experimental studies have several limitations:
• It is necessary to implement and test
the algorithm in order to determine its
running time.
• Experiments can be done only on a
limited set of inputs, and may not be
indicative of the running time on other
inputs not included in the experiment.
• In order to compare two algorithms, the
same hardware and software
environments should be used.
2012-2013
8
Beyond Experimental Studies
• We will now develop a general methodology for
analyzing the running time of algorithms. In
contrast to the "experimental approach", this
methodology:
• Uses a high-level description of the
algorithm instead of testing one of its
implementations.
• Takes into account all possible inputs.
• Allows one to evaluate the efficiency of
any algorithm in a way that is
independent from the hardware and
software environment.
2012-2013
9
Pseudo-code
• Pseudo-code is a description of an algorithm that is more
structured than usual prose but less formal than a programming
language.
• Example: finding the maximum element of an array.
Algorithm arrayMax(A, n):
Input: An array A storing n integers.
Output: The maximum element in A.
currentMax  A[0]
for i 1 to n -1 do
if currentMax < A[i] then currentMax  A[i]
return currentMax
• Pseudo-code is our preferred notation for describing algorithms.
• However, pseudo-code hides program design issues.
2012-2013
10
What is Pseudo-code?
• A mixture of natural language and high-level programming
concepts that describes the main ideas behind a generic
implementation of a data structure or algorithm.
Expressions:
• use standard mathematical symbols to describe
boolean expressions
•
numeric and
use  for assignment (“=” in Java)
• use = for the equality relationship (“==” in Java)
Method Declarations:
•
2012-2013
Algorithm name(param1, param2)
11
What is Pseudo-code?
• Programming Constructs:
• decision structures:
if ... then ... [else ]
• while-loops:
while ... Do
• repeat-loops:
repeat ... until …
• for-loop:
• array indexing:
for ... Do
A[i]
• Functions/Method
calls:
object method(args)
returns: return value
2012-2013
12
Analysis of Algorithms
• Primitive Operations: Low-level computations independent
from the programming language can be identified in
pseudocode.
• Examples:
• calling a function/method and returning from a
function/method
• arithmetic operations (e.g. addition)
• comparing two numbers
• indexing into an array, etc.
•
2012-2013
By inspecting the pseudo-code, we can count the
number of primitive operations executed by an algorithm.
13
Example: Sorting
OUTPUT
INPUT
a permutation of the
sequence of numbers
sequence of numbers
a1, a2, a3,….,an
2
5
4
10
Sort
7
Correctness
For any given input the algorithm
halts with the output:
• b1 < b2 < b3 < …. < bn
• b1, b2, b3, …., bn is a
permutation of a1, a2, a3,….,an
2012-2013
b1,b2,b3,….,bn
2
4
5
7
10
Running time
Depends on
• number of elements (n)
• how (partially) sorted
they are
• algorithm
14
Insertion Sort
A
3
4
6
8
9
1
7
2
j
5 1
n
i
Strategy
• Start “empty handed”
• Insert a card in the right
position of the already sorted
hand
• Continue until all cards are
inserted/sorted
2012-2013
for j=2 to length(A)
do key=A[j]
“insert A[j] into the
sorted sequence A[1..j-1]”
i=j-1
while i>0 and A[i]>key
do A[i+1]=A[i]
i-A[i+1]:=key
15
Analysis of Insertion Sort
• Time to compute the running time as a function of
the input size
• Total Time= n(c1+c2+c3+c7)+ j  2 t j (c4+c5+c6)(c2+c3+c5+c6+c7)
n
for j=2 to length(A)
do key=A[j]
“insert A[j] into the
sorted sequence A[1..j-1]”
i=j-1
while i>0 and A[i]>key
do A[i+1]=A[i]
i-A[i+1]:=key
2012-2013
cost
c1
c2
0
c3
c4
c5
c6
c7
times
n
n-1
n-1
n-1
 nj  2 t j
 nj 2 (t j  1)
 j 2 (t j  1)
n-1
n
16
Best/Worst/Average Case
• Best case: elements already sorted  tj=1, running
time = f(n), i.e., linear time.
• Worst case: elements are sorted in inverse order
 tj=j, running time = f(n2), i.e., quadratic time
• Average case: tj=j/2, running time = f(n2), i.e.,
quadratic time
Total Time= n(c1+c2+c3+c7)+  j  2 t j
(c4+c5+c6)-(c2+c3+c5+c6+c7)
n
2012-2013
17
Best/Worst/Average Case (2)
• For a specific size of input n, investigate running times for different
input instances:
6n
5n
4n
3n
2n
1n
2012-2013
18
Best/Worst/Average Case (3)
• For inputs of all sizes:
worst-case
average-case
Running time
6n
5n
best-case
4n
3n
2n
1n
1
2
3
4
5
6
7
8
9 10 11 12 …..
Input instance size
2012-2013
19
Best/Worst/Average Case (4)
• Worst case is usually used:
• It is an upper-bound and in certain application
domains (e.g., air traffic control, surgery)
knowing the worst-case time complexity is of
crucial importance
• For some algorithms worst case occurs fairly
often
• The average case is often as bad as the worst
case
• Finding the average case can be very difficult
2012-2013
20
Asymptotic Notation
• Goal: to simplify analysis by getting rid of unneeded
information (like “rounding” 1,000,001≈1,000,000)
• We want to say in a formal way 3n2 ≈ n2
• The “Big-Oh” Notation:
• given functions f(n) and g(n), we say that f(n) is O(g(n)) if
and only if there are positive constants c and n0 such that
f(n)≤ c g(n) for n ≥ n0
2012-2013
21
Asymptotic Notation
• The “big-Oh” O-Notation
• asymptotic upper bound
• f(n) = O(g(n)), if there exists constants
c and n0, s.t. f(n)  c g(n) for n  n0
• f(n) and g(n) are functions over nonnegative integers
Running
Time
• Used for worst-case analysis
c  g ( n)
n0
2012-2013
f (n )
Input
Size
22
Example
For functions f(n) and
g(n) (to the right)
there are positive
constants c and n0
such that: f(n)≤ c g(n)
for n ≥ n0
conclusion:
f(n) = 2n + 6
c g(n )  4n
g(n)  n
2n+6 is O(n).
n
2012-2013
23
Another Example
On the other hand…
n2 is not O(n) because there is
no c and n0 such that:
n2 ≤ cn for n ≥ n0
(As the graph to the right
illustrates, no matter how large
a c is chosen there is an n big
enough that n2>cn ) .
2012-2013
24
Asymptotic Notation (cont.)
• Note: Even though it is correct to say “7n - 3 is
O(n3)”, a better statement is “7n - 3 is O(n)”, that is,
one should make the approximation as tight as
possible (for all values of n).
• Simple Rule: Drop lower order terms and
constant factors
7n-3 is O(n)
8n2log n + 5n2 + n is O(n2log n)
2012-2013
25
Asymptotic Analysis of The Running Time
• Use the Big-Oh notation to express the number of
primitive operations executed as a function of the input
size.
• For example, we say that the arrayMax algorithm runs
in O(n) time.
• Comparing the asymptotic running time
-an algorithm that runs in O(n) time is better than one that runs in O(n2)
time
-similarly, O(log n) is better than O(n)
-hierarchy of functions: log n << n << n2 << n3 << 2n
• Caution! Beware of very large constant factors. An
algorithm running in time 1,000,000 n is still O(n) but
might be less efficient on your data set than one
running in time 2n2, which is O(n2)
2012-2013
26
Example of Asymptotic Analysis
An algorithm for computing prefix averages
Algorithm prefixAverages1(X):
Input: An n-element array X of numbers.
Output: An n -element array A of numbers such that A[i] is the
average of elements X[0], ... , X[i].
Let A be an array of n numbers.
for i 0 to n - 1 do
a0
for j  0 to i do
a  a + X[j]
A[i]  a/(i+ 1)
return array A
• Analysis ...
2012-2013
1 step
i iterations
with
i=0,1,2...n-1
n iterations
27
Another Example
• A better algorithm for computing prefix averages:
Algorithm prefixAverages2(X):
Input: An n-element array X of numbers.
Output: An n -element array A of numbers such that A[i] is the
average of elements X[0], ... , X[i].
Let A be an array of n numbers.
s 0
for i  0 to n do
s  s + X[i]
A[i]  s/(i+ 1)
return array A
• Analysis ...
2012-2013
28
Asymptotic Notation (terminology)
• Special classes of algorithms:
logarithmic:
linear:
O(log n)
O(n)
quadratic: O(n2)
polynomial:
O(nk), k ≥ 1
exponential:
O(an), n > 1
• “Relatives” of the Big-Oh
•  (f(n)): Big Omega--asymptotic lower bound
•  (f(n)): Big Theta--asymptotic tight bound
2012-2013
29
Growth Functions
1,00E+10
1,00E+09
1,00E+08
n
log n
sqrt n
n log n
100n
n^2
n^3
1,00E+07
T(n)
1,00E+06
1,00E+05
1,00E+04
1,00E+03
1,00E+02
1,00E+01
1,00E+00
1,00E-01
2
4
8
16
32
64
128
256
512
1024
n
2012-2013
30
Growth Functions (2)
1,00E+155
1,00E+143
1,00E+131
1,00E+119
n
log n
sqrt n
n log n
100n
n^2
n^3
2^n
1,00E+107
T(n)
1,00E+95
1,00E+83
1,00E+71
1,00E+59
1,00E+47
1,00E+35
1,00E+23
1,00E+11
1,00E-01
2
4
8
16
32
64
128
256
512
1024
n
2012-2013
31
Asymptotic Notation (2)
• The “big-Omega” Notation
• asymptotic lower bound
• Used to describe best-case running
times or lower bounds of algorithmic
problems
• E.g., lower-bound of searching in
an unsorted array is (n).
Running
Time
• f(n) = (g(n)) if there exists
constants c and n0, s.t. c g(n) 
f(n) for n  n0
f (n )
c  g ( n)
n0
2012-2013
Input
Size
32
Asymptotic Notation (4)
• The “big-Theta” Notation
• asymptoticly tight bound
• f(n) = (g(n)) if there exists
constants c1, c2, and n0, s.t. c1
g(n)  f(n)  c2 g(n) for n  n0
• O(f(n)) is often misused instead of
(f(n))
Running
Time
• f(n) = (g(n)) if and only if f(n) =
O(g(n)) and f(n) = (g(n))
c 2  g (n )
f (n )
c 1  g (n )
n0
2012-2013
Input
Size
33
Asymptotic Notation (5)
• Two more asymptotic notations
• "Little-Oh" notation f(n)=o(g(n))
non-tight analogue of Big-Oh
• For every c, there should exist n0 , s.t. f(n)  c g(n) for n 
n0
• Used for comparisons of running times. If f(n)=o(g(n)), it
is said that g(n) dominates f(n).
• "Little-omega" notation f(n)=w(g(n))
non-tight analogue of Big-Omega
2012-2013
34
Asymptotic Notation (6)
• Analogy with real numbers
• f(n) = O(g(n))
@
f g
• f(n) = (g(n))
@
fg
• f(n) = (g(n))
@
f g
• f(n) = o(g(n))
@
f <g
• f(n) = w(g(n))
@
f >g
• Abuse of notation: f(n) = O(g(n)) actually means
f(n) O(g(n))
2012-2013
35
Comparison of Running Times
2012-2013
Running
Time in
ms
Maximum problem size (n)
1 second
1 minute
1 hour
400n
2500
150000
9000000
20n log n 4096
166666
7826087
2n2
707
5477
42426
n4
31
88
244
2n
19
25
31
36
Math You Need to Review
Logarithms and Exponents
• properties of logarithms:
logb(xy) = logbx + logby
logb (x/y) = logbx - logby
logbxa = alogbx
Logba = logxa/logxb
• properties of exponentials:
a(b+c) = abac
abc = (ab)c
ab/ac = a(b-c)
b = a logab
bc = a c*logab
2012-2013
37
A Quick Math Review
• Geometric progression
• given an integer n0 and a real number 0< a  1
n 1
1

a
i
2
n
a

1

a

a

...

a


1 a
i 0
n
• geometric progressions exhibit exponential growth
• Arithmetic progression
n(1  n)
i  1  2  3  ...  n 

2
i 0
n
2012-2013
38
Summations
• The running time of insertion sort is determined by a
nested loop
for j2 to length(A)
keyA[j]
ij-1
while i>0 and A[i]>key
A[i+1]A[i]
ii-1
A[i+1]key
• Nested loops correspond to summations
2
(
j

1)

O
(
n
)
 j 2
n
2012-2013
39
Proof by Induction
• We want to show that property P is true for all
integers n  n0
• Basis: prove that P is true for n0
• Inductive step: prove that if P is true for all k such
that n0  k  n – 1 then P is also true for n
• Example
n(n  1)
S ( n)   i 
for n  1
2
i 0
n
• Basis
1(1  1)
S (1)   i 
2
i 0
1
2012-2013
40
Proof by Induction (2)
• Inductive Step
k ( k  1)
S (k )   i 
for 1  k  n  1
2
i 0
k
n
n 1
i 0
i 0
S ( n)   i  i  n S ( n  1)  n 
( n  1  1)
( n 2  n  2 n)
 ( n  1)
n

2
2
n( n  1)

2
2012-2013
41
Thank You
2012-2013
42