Transcript cn used tower

Technische Universität Darmstadt
Telecooperation/RBG
Introduction to Computer Science I
Topic 7: Complexity of Algorithms
Prof. Dr. Max Mühlhäuser
Dr. Guido Rößling
Copyrighted material; for TUD student use only
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Algorithm Selection
Two algorithms solve the same problem.
Example: merge-sort and insertion-sort
Which one is the "better" one?
We need to consider
non-functional
properties of algorithm:
• Time complexity
In the following, we will
concentrate on "time". Analog
treatment of "space"
– How long does the execution take?
• Space complexity
– How much memory is required for execution?
• Required network bandwidth
Introduction to Computer Science I: T7
2
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
How to measure the cost of computing?
• Timing the application of a program to specific
arguments can help to understand its behavior in one
situation
– However, applying the same program to other inputs may
require a radically different amount of time…
• Timing programs for specific inputs has the same status
as testing programs for specific examples:
– Just like testing may reveal bugs, timing may reveal anomalies
of the execution behavior for specific inputs
– It does not, however, provide a foundation for general
statements about the behavior of a program
• This lecture provides a first glimpse at tools for making
general statements about the cost of programs
– ICS 2 provides more in-depth considerations
Introduction to Computer Science I: T7
3
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Outline
•
•
•
•
Abstract time for complexity analysis
O-Notation and other notations for asymptotic growth
Techniques for measuring algorithm complexity
Vectors in Scheme
Introduction to Computer Science I: T7
4
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Concrete Time, Abstract Time
“Real time" execution depends on many factors
– speed of computer
To allow a reasonable
– type of computer
comparison between
– programming language
different algorithms for
– quality of compiler, …
the same problem, we
need a way of measuring
Real time (milliseconds)
for computing some f
time complexity that is
independent of all such
Time
computer type
factors
•
Home computer
Desktop Computer
Minicomputer
Mainframe computer
Supercomputer
51.915
11.508
2.382
0.431
0.087
Real execution time
(milliseconds) for computing f
Introduction to Computer Science I: T7
5
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Measuring Complexity
• Idea: Describe resource consumption as a mathematical
function  cost function
• Domain of the cost function: Size of the input n
– Depends on the problem being studied:
• for sorting a list, n = number of list items
• for matrix multiplication n = number of rows and
m = number of columns
• for graph algorithms, n = number of nodes,
e = number of edges
• Range of the cost functions: Required number of
computation steps T(n)
• Number of natural recursions is a good measure of the size of an
evaluation sequence.
Introduction to Computer Science I: T7
6
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Illustrating Abstract Time
• Let us study the behavior of length, a function that we
understand well:
– It takes a list of arbitrary data and computes how many items the list
contains
(define (length a-list)
(cond
[(empty? a-list) 0]
[else (+ (length (rest a-list)) 1)]))
= (+ (length (list 'b 'c)) 1)
= (+ (+ (length (list 'c)) 1) 1)
= (+ (+ (+ (length empty) 1) 1) 1)
= 3
Introduction to Computer Science I: T7
natural recursion
steps
length (list 'a 'b 'c))
7
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
Illustrating Abstract Time
©
• Only steps that are natural recursions are relevant for
the complexity judgment.
=
=
=
=
=
• The steps between the natural recursions differ only as far as the
substitution for a-list is concerned.
(length (list 'a 'b 'c))
(cond
[(empty? (list 'a 'b 'c)) 0]
[else (+ (length (rest (list 'a 'b 'c))) 1)])
(cond
[false 0]
[else (+ (length (rest (list 'a 'b 'c))) 1)])
(cond
[else (+ (length (rest (list 'a 'b 'c))) 1)])
(+ (length (rest (list 'a 'b 'c))) 1)
(+ (length (list 'b 'c)) 1)
Introduction to Computer Science I: T7
8
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Illustrating Abstract Time
• The example suggests two things:
– The number of evaluation steps depends on input size
– The number of natural recursions is a good measure of the size of an
evaluation sequence.
• After all, we can reconstruct the actual number of steps from this
measure and the function definition
• The abstract running time measures the performance of a
program as a relationship between the size of the input and the
number of recursion steps in an evaluation
– “abstract” means: the measure ignores the details of constant
factors
• how many primitive steps are needed
• how much time primitive steps take
• and how much “real“ time the overall evaluation takes.
Introduction to Computer Science I: T7
9
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
Abstract Time and the Input Shape
©
(define (contains-doll? alos)
(cond
[(empty? alos) false]
[(symbol=? (first alos) 'doll) true]
[else (contains-doll? (rest alos))]))
• The following application requires no recursion step
(contains-doll? (list 'doll 'robot 'ball 'game-boy))
• In contrast, the evaluation below requires as many
recursion steps as there are items in the list
(contains-doll? (list 'robot 'ball 'game-boy 'doll))
• In the best case, the function finds an answer immediately
• In the worst case, the function must search the entire
input list
Introduction to Computer Science I: T7
10
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
Abstract Time and the Input Shape
©
• Programmers cannot safely assume that inputs are
always of the best possible type
– They also cannot just hope that the inputs will not be of the
worst possible type
• Instead, they must analyze how much time their
functions take on average
• For example, contains-doll? may - on average find 'doll somewhere in the middle of the list
– If the input contains n items, the abstract running time of
contains-doll? is (in average) n/2
• On average, there are half as many recursion steps as there are
elements in the list
Introduction to Computer Science I: T7
11
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
Complexity Classes
©
• Because we measure the running time of a function in
an abstract manner, we can ignore the division by 2.
• More precisely,
– We assume that each basic step takes K units of time
– If we use K/2 as
the constant, then:
n K
K*  *n
2 2
• To indicate that we are hiding such constants we say
that contains-doll? takes "on the order of n steps
(~ n)'' to find 'doll in a list of n items.

12
Introduction to Computer Science I: T7
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Complexity Classes
F ~ on the order of n
G ~ on the order of n2
G
F
T
0
n
1000
n
1
10
50
1000
500
F (1000 · n)
1000
10000
50000
500000
1000000 5000000
G (n · n)
1
100
2500
250000
1000000 25000000
Introduction to Computer Science I: T7
5000
13
Analysis: insertion-sort
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
;; insertion-sort : list-of-numbers -> list-of-numbers
;; creates a sorted list of numbers from numbers in alon
(define (insertion-sort alon)
(cond
[(empty? alon) empty]
[else (insert (first alon)
(insertion-sort (rest alon)))]))
=
=
=
=
=
=
=
=
=
(sort (list 3 1 2))
(insert 3 (insertion-sort (list 1 2)))
(insert 3 (insert 1 (insertion-sort (list 2))))
(insert 3 (insert 1 (insert 2 (insertion-sort empty))))
(insert 3 (insert 1 (insert 2 empty)))
(insert 3 (insert 1 (list 2)))
(insert 3 (cons 1 (list 2)))
(insert 3 (list 1 2)) = (cons 1 insert 3 (list 2))
(cons 1 (cons 2 (insert 3 empty)))
(list 1 2 3)
Introduction to Computer Science I: T7
14
Analysis: insert-sort
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
• The evaluation consists of two phases:
1. The recursions for sort set up as many applications of insert as
there are items in the list
2. Each application of insert traverses a list of 1, 2,...n - 1
elements, where n is the number of items in the original list
• Inserting an item is similar to finding an item:
–
–
Applications of insert to a list of n items may trigger on the
average, n/2 natural recursions, i.e., ~ n.
Because there are n applications of insert, we have an average
of ~ n2 natural recursions of insert
• In summary, if lst contains n items,
–
–
–
evaluating (insert-sort lst) requires n natural recursions of
insert-sort and
on the order of n2 natural recursions of insert.
Taken together: n2 + n, i.e. ~ n2
Introduction to Computer Science I: T7
15
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Complexity Classes
• We know that insert-sort takes time roughly equal to
c1n2 to sort n items (proportional to n2)
– c1 is a constant that does not depend on n
• We now analyze the efficiency of merge-sort
– It takes time roughly equal to c2n log n for n items
• c2 is a constant that does not depend on n,
• c 2 > c1
– No matter how much smaller c1 is than c2, there will always be a
crossover point in the input data (n “big enough”) beyond which
merge-sort is faster
– Hence, we can safely ignore constants
Introduction to Computer Science I: T7
16
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Complexity Classes
• Imagine that we used a very fast computer A for
running insert-sort and a slow computer B for
merge-sort
– A is 100 times faster than B in raw computing power
• A executes one billion (109) instructions per second
• B executes only ten million (107) instructions per second
• In addition, we assume that
– The best programmer in the world codes insert-sort in machine
language for A
• The resulting code requires 2n2 (c1 = 2) instructions to sort n
numbers
– An average programmer codes merge-sort in a high-level
language with an inefficient compiler
• resulting code requires 50n log n (c2 = 50) instructions
Introduction to Computer Science I: T7
17
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Complexity Classes
To sort a list of one million numbers (n = 106) …
A (insert-sort)
2 x (106)2 instructions
109
instructions/sec
=
2000 sec
B (merge-sort)
50 x 106 x log2 106 instructions
107
instructions/sec
≈ 100 sec
By using an algorithm whose running time grows more slowly,
even with a poor compiler, B runs 20 times faster than A!
In general, as the problem size increases, so does the relative
advantage of merge-sort.
Introduction to Computer Science I: T7
18
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Summary: abstract running time
• Our abstract description is always a claim about the
relationship between two quantities:
– A (mathematical) function that maps an abstract size
measure of input to an abstract measure of running time
(number of natural recursions evaluated)
• The exact number of executed operations is less
important
• It is important to know the complexity class to
which the algorithm belongs
– e.g., linear or logarithmic
• When we compare “on the order of” properties of
procedures, such as n, n2, 2n,…, we mean to
compare corresponding functions that use n and
produce the above results
Introduction to Computer Science I: T7
19
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Outline
•
•
•
•
Abstract time for complexity analysis
O-Notation and other notations for asymptotic growth
Techniques for measuring algorithm complexity
Vectors in Scheme
Introduction to Computer Science I: T7
20
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
O-Notation
• Comparing functions on N is difficult
– The domain of N is infinite
– If a function f produces larger outputs than some function g for
all n in N, then f is clearly larger than g
– But what if comparison fails for a few inputs, e.g.,1000?
• To make approximate judgments,
G
– we adapt the mathematical notion
of comparing functions
T
– up to some factor
– and some finite number of exceptions
0
Introduction to Computer Science I: T7
F
1000
n
21
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
O-Notation
ORDER-OF (BIG-O):
Given a function g on the natural numbers, O(g) (pronounced:
“big-O of g”) denotes a class of functions on natural numbers.
A function f is in O(g) if there exist numbers c and n0 = bigEnough
such that for all n > n0, it is true that f(n) <= cg(n)
• The „O-Notation“ goes back to the number theoretician
Edmund Landau (1877-1938); the "O" is also called the
„Landau Symbol“
• We say that "f(n) grows at least as quickly as g(n)"
(g is an upper bound for f)
Introduction to Computer Science I: T7
22
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
O-Notation
©
f is at most of order g (n)
f(n)  O(g(n)), if two positive constants, C and n0
exist, where |f(n)|  C|g(n)| for all n  n0
3000
2000
1000
function f
asymptotically
behaves like g;
from n0 on, it is
always < C g(n)
function g
defines the
complexity class
f(n)
0
125 250
500
1000
n0
C g(n)
Introduction to Computer Science I: T7
An asymptotic measure
(n  ). It abstracts
from irrelevant details
for 2000
the complexity
class
23
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
O-Notation: Examples
• For f(n) = 1000*n and g(n)=n2 we can say that f
is in O(g), because for all n > 1000,
• f(n) <= c.g(n)
(n0 = 1000 and c = 1)
• The definition of big-O provides us with a shorthand for
stating claims about a function's running time:
– The running time of length is in O(n).
• n is the abbreviation of the (mathematical) function g(n) = n
– In the worst case, the running time of insert-sort is O(n2)
– Here, n and n2 are standard abbreviations for the
(mathematical) functions f(n) = n and g(n) =n2
Introduction to Computer Science I: T7
24
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Complexity Classes
O(n2)
O(n log n)
O(n)
number of comparisons
O(n3)
O(log n)
input size (n)
• polynomial growth (O (nx)) drastically reduces the
useful input size
• exponential growth (O(en)) even more so
Introduction to Computer Science I: T7
25
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Properties of the O-Notation
• Comparison of "O" complexity are only useful for large
input sizes
- For small input sizes, an inefficient algorithm may be faster
than an efficient one
- E.g., a function in 2n2
grows faster than
Heap
a function in (184 log2n),
Insertion
but is better for small
input
sizes (n<20)
1800
1600
1400
1200
1000
800
600
400
200
0
1
3
5
7
9
11
13
15
17
19
21
23
25
27
• Algorithms with linear or even weaker growth rate are
sensitive against such factors
- Comparing the complexity class may be insufficient in such
cases
Introduction to Computer Science I: T7
26
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
Properties of the O-Notation
- The Notation neglects proportional factors, small
input sizes, and smaller terms
n
10
125
250
500
1000
2000
f(n) = an2 + bn +c
with a = 0.0001724, b = 0.0004 and c = 0.1
n2 - term in %
f(n)
an2
of the whole
0.121
0.017
14.2
2.8
2.7
94.7
11.0
10.8
98.2
43.4
43.1
99.3
172.9
172.4
99.7
690.5
689.6
99.9
Beispiele:
2n3+n2-20
 O(n3)
log10 n  O(log2 n)
n + 10000
 O(n)
n  O(n2)
O(1)  O(log n)  O(n)  O(n2)  O(n3)  O(2n)  O(10n)
Introduction to Computer Science I: T7
©
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
O-Notation: Other Symbols
• There are other symbols for different needs:
• Asymptotic lower bound [f(n)  (g(n))]:
• f(n)  (g(n)) if  positive constants c and n0 such that
 cg(n)  f(n)  n  n0
• "f(n) grows at least as quickly as g(n)”
0
– Asymptotic tight bound [f(n)  (g(n))]:
• f(n)  (g(n)) if  positive constants c1, c2, and n0 such that
c1 g(n)  f(n)  c2 g(n)  n  n0
• f(n)  (g(n)) if and only if f(n)  O(g(n)) and f(n)  (g(n))
• "f(n) grows as quickly as g(n)"
Introduction to Computer Science I: T7
28
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
O-Notation: Other Symbols
• Schema for O,  and :
n0
upper bound
n0
lower bound
Introduction to Computer Science I: T7
n0
exact bound
29
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Other Asymptotic Notations
• A function f(n) is o(g(n)) if positive constants c and n0
exist such that
f(n) < c g(n)  n  n0
• A function f(n) is (g(n)) if positive constants c and n0
exist such that
c g(n) < f(n)  n  n0
• Intuitively,
– o() is like <
– O() is like 
– () is like >
– () is like 
– () is like =
Introduction to Computer Science I: T7
30
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Outline
•
•
•
•
Abstract time for complexity analysis
O-Notation and other notations for asymptotic growth
Techniques for measuring algorithm complexity
Vectors in Scheme
Introduction to Computer Science I: T7
31
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Example: GCD
(define (gcd a b)
(cond
[(= b 0) a]
[else (gcd b (remainder a b))]))
• Complexity analysis of Euclid’s algorithm gcd is highly
non-trivial
• Lamé’s Theorem:
– If Euclid’s Algorithm requires k steps to compute the gcd of
some pair, then the smaller number in the pair must be greater
than or equal to the k-th Fibonacci number
– Hence, if n is the smaller number in the pair, n Fib(k)  k
• Order of growth is O(log(n))
Introduction to Computer Science I: T7
32
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Example: Exponentiation
• Input: Base b, positive integer exponent n
• Output: bn
• Idea: bn = b* b(n-1) , b0 = 1
(define (expt b n)
(cond
[(= n 0) 1]
[else (* b (expt b (- n 1)))]))
• Assume multiplication needs a constant time c
• Time: T(n) = cn = O(n)
Introduction to Computer Science I: T7
33
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Example: Faster Exponentiation
• Idea: Use fewer steps with successive squaring
– Example: instead of computing b8 as b*b*b*b*b*b*b*b we can
compute it as
b2 = b*b, b4 = (b2)2,
b8 = (b4)2
– In general we can use the rule
• bn = (bn/2) 2
if n is even
bn = b*bn-1
if n is odd
(define (fast-expt b n)
(cond [(= n 0) 1]
[(even? n) (sqr (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
• What is the time complexity class of this algorithm?
Introduction to Computer Science I: T7
34
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Analyzing divide-and-conquer-algorithms
• The running time of a recursive algorithm can often be described
by a recurrence equation or recurrence
– A recurrence describes overall running time in terms of the running
time on smaller inputs
– Example:
• Problem (n) is devided into 2 sub problems (n/2)
• Complexity cn for deviding and combination of the sub solutions
c



T ( n)  
2T  n   cn

 2
n 1
n 1
• A recurrence for the running time, T(n), of a divide-and-conquer
algorithm on a problem of size n is based on the three steps of the
paradigm…
Introduction to Computer Science I: T7
35
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Analyzing divide-and-conquer-algorithms
• Case 1: Problem size is small enough, say n <= c for
some constant c, so that it can be solved trivially
 Direct solution takes constant time  (1)
• Case 2: Problem is non-trivial:
– The division of the problem yields a sub-problems, each of
which is 1/b of the size of the original problem
• Example: for merge-sort we have a = b = 2
– D(n): time to divide the problem into sub-problems
– C(n): time to combine the solutions of sub-problems
(1)



T ( n)  
aT  n   D(n)  C (n)

 b
Introduction to Computer Science I: T7
nc
sonst
36
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Towers of Hanoi
!
The “Towers of Hanoi” puzzle was invented by the french
mathematician Édouard Lucas
We have a tower of discs are stacked on a rod in order of size, the
tmallest on top.
The objective is to transfer the entire tower to one of the other pegs,
moving only one disk at a time and never a larger one onto a
smaller.
Introduction to Computer Science I: T7
37
Towers of Hanoi: Algorithm
1
A
B
To
1.
2.
3.
©
C
3
2
n
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
move n discs from rod A to rod B:
move n−1 discs from A to C. This leaves disc #n alone on peg A
move disc #n from A to B
move n−1 discs from C to B so they sit on disc #n
Recursive algorithm: to carry out steps 1 and 3, apply the same
algorithm again for n−1. The entire procedure is a finite number of
steps, since at some point the algorithm will be required for n = 1.
This step, moving a single disc from peg A to peg B, is trivial.
Introduction to Computer Science I: T7
38
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
Towers of Hanoi
©
(move 'A 'B 'C 4)
(define (move T1 T2 T3 n)
(cond
(list
[(= n 0) empty]
(list 'A 'C)
[else
(list 'A 'B)
(append
(list 'C 'B)
(move T1 T3 T2 (- n 1))
(list 'A 'C)
(list (list T1 T2))
(list 'B 'A)
(move T3 T2 T1 (- n 1)))
(list 'B 'C)
]
(list 'A 'C)
)
(list 'A 'B)
)
Result is the list of disc movements
(list 'C 'B)
(list 'C 'A)
A
C
B
(list
(list
(list
(list
(list
How many disk movements are required for
moving a stack of height n?
Introduction to Computer Science I: T7
'B
'C
'A
'A
'C
'A)
'B)
'C)
'B)
'B))
39
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Solving the Recurrence for Towers of Hanoi
• How many disk movements are required for moving a
stack of height n from pole 1 to pole 2?
- for n<2 the answer is easy: T(0)=0, T(1)=1
- for n>1 the answer is recursively defined:
T(n) = T(n-1)+1+T(n-1) = 2×T(n-1)+1
= 2×(2×T(n-2)+1)+1 = 2×(2×(2×T(n-3)+1)+1)+1
i-1
= 2i×T(n-i) + 2k , for i=n, n-i becomes 0
k0
= 2n×T(0) + 2n-1 = 2n-1
=> exponential complexity!
Introduction to Computer Science I: T7
40
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
When the universe will end…
There is a legend about a buddhistic temple near Hanoi.
In this temple there is a room with three nagged rods
with 64 golden discs.
– Since the temple was founded some thousand years ago, the
monks act on an old prophecy:
• They move the discs according to the rules of the puzzle
• Each day the monks move a single disc
– It is said that they believe that the universe will end once they
moved the last disc.
Introduction to Computer Science I: T7
41
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Solving the Recurrence for Towers of Hanoi
The monks are nowhere close to completion 
Even if the monks were able to move discs at a rate of one per
second, using the smallest number of moves:
• it would take 264 − 1 seconds or ~ 585 billion years!
• The universe is currently about 13.7 billion years old
Introduction to Computer Science I: T7
42
Analysis of Merge Sort
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
• Simplification: We assume for the analysis that the original
problem size is a power of 2
– Each divide step then yields two sub-sequences of exactly n/2
– There are proofs that such an assumption does not affect the order
of growth of the solution to the recurrence
• Worst case: n > 1
– Divide: Extracting the elements of the two sub-lists takes on the
order of n time each  D(n) = 2n ~ (n)
– Conquer: To recursively solve two sub-problems, each of size n/2
requires 2T(n/2)
– Combine: merging two lists takes also on the order of (n)
(1)
n 1

worst-case

T ( n)  
running time
2T  n   (n) n  1
for merge sort
  2 
Introduction to Computer Science I: T7
43
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Solving Recurrences
• Question: How does one solve recurrences such as the
one we constructed for the running time of merge sort?
• Answer: Mathematical methods help us with this:
– Substitution method
– Recursion tree method
– Master method based on master theorem
• A “recipe" to solve recurrences of the form
T(n) = aT(n/b)+f(n), a ≥1, b>1, f(n) asymptotically
positive function
• It can be used to show that T(n) of merge sort is (n log n)
• We neglect technical details:
– ignore ceilings and floors (all absorbed in the O or  notation)
– We assume integer arguments to functions
– Boundary conditions
Introduction to Computer Science I: T7
44
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
The Master Theorem
Consider
(1)

T ( n)  
aT (n / b)  f (n)
if n < c
if n > 1
where a >= 1 and b >= 1
logb a e
f
(
n
)

O
(
n
) for some constant e > 0
• If
then T (n)  (n logb a )
• If f (n)  O(nlog a ) then T (n)  (nlog a log n)
logb a e
• If f (n)  O(n
) for some constant e > 0
b
b
and if a f(n/b) <= c f(n) for some constant c < 1
and all n sufficiently large, then T(n) =(f (n))
Introduction to Computer Science I: T7
45
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
The Recursion Tree Method
• In a recursion tree, each node represents the cost of a
single sub-problem somewhere in the set of recursive
function invocations
– Sum costs within each level to get per-level costs
– Sum all per-level costs to determine the total cost
• Particularly useful method for recurrences that describe
running time of divide-and-conquer algorithms
• Often used to make a good guess that is then verified by
other methods
– When built carefully, can also be used to as a direct proof of a
solution to a recurrence
Introduction to Computer Science I: T7
46
Recursion Tree for Merge Sort
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Let us write the recurrence for merge-sort as:
Node for 1st recursive call
c
n 1


T ( n)  
2T  n   cn n  1
  2 
cn
T(n/2) T(n/2)
Tree for two recursive steps
cn
cn/2
cn/2
T(n/4) T(n/4) T(n/4) T(n/4)
Introduction to Computer Science I: T7
47
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
Recursion Tree for Merge Sort
cn
cn
cn/2
cn/4
cn
cn/2
cn/4
cn/4
cn
cn/4
...
...
...
...
...
...
...
2ic(n/2i)
...
...
...
c c
c
c
c
c
n
Introduction to Computer Science I: T7
...
...
c
...
...
...
Level i  2i nodes
...
levels
(by induction)
...
log n + 1
...
Total:
cn (log n + 1)
©
c
cn
48
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
The Substitution Method
• A.k.a. the “making a good guess method”
• Functionality
– Guess the form of the answer
– Use induction to find the constants and show that solution
works
• Examples:
• T(n) = 2T(n/2) + (n)  T(n) = (n log n)
• T(n) = 2T(n/2) + n  T(n)
•
??? = (n log n)
• T(n)
T(n) == 2T(n/2+
2T(n/2 +17)
17)++nn(n
??? log n)
Introduction to Computer Science I: T7
49
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
The Substitution Method
©
Recurrence
Guessed solution
T(n)  2T n /2 n
T(n)  (nlog n)
We need to prove that T(n)  cnlog n
for an appropriate choice of the constant c > 0
We start by assuming 
that this bound holds for n / 2
 cn /2log n /2
that is: T n /2
T(n)  2T n /2 n


 2 cn /2log n /2  n

 cn log n /2  n
 cn log n  cn log 2  n
 cn log n  cn  n
 cn log n
n  1  1  T (1)  c1 log 1  0 ???
Solution: we need to prove
the guess for n>n0
n  2  T(2)  2T(1)  2  4
T(2)  c2log 2  c2  c  2
c 1
Introduction to Computer Science I: T7
50
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Performance of Quick Sort: Best Case
• Runtime of quick-sort depends on quality of
partitioning, i.e., on the elements used as pivots
• Best case: partition produces in each step two subproblems of size n/2
T (n)  2T (n / 2)  (n)
master
theorem
T(n)  (nlog n)

Introduction to Computer Science I: T7
51
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
Performance of Quick Sort: Worst Case
©
• Worst case: partitioning produces one sub-problem with
n-1 and one with 0 elements in each recursive step
Worst case occurs when the list is already sorted!
Let partition time be (n), recursive call on empty list  T(0) = (1)
☞ T(n) = T(n-1)+T(0)+(n)
= T(n-1)+(n)
- Intuitively, summing per-level
costs yields an arithmetic
series, which evaluates to
(n2)
n
1
n-1
1
n
n-2
1
n-2
n-3
1
 n 
n    k   1  (n)  (n 2 )  (n)  (n 2 )
 k 1 
Introduction to Computer Science I: T7
n
n
n-1
3
2
1
1
2
(n2)
52
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Performance of Quick Sort: Balanced Partitioning
• Average case of quick-sort is much closer to the
best case. It uses Θ(nlogn) comparisons to sort n
items.
• To understand why, we need to see how the
partitioning balance is reflected in the recurrence
of quick-sort for the running time
• Balanced partitioning: Partitioning always produces
a constant split
Introduction to Computer Science I: T7
53
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
Performance of Quick Sort: Balanced Partitioning
©
• E.g.: 9-to-1 proportional split  seems quite unbalanced
T(n) <= T(9n/10) + T(n/10) + n
Even a 99:1
split yields
O(n log n)
(log n)
Reason: splits of constant proportionality yield
recursive trees of depth (log n) with the
cost at each level O(n)
Introduction to Computer Science I: T7
54
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Performance of Quick Sort: Average Case
• Intuition for the average case
– All permutations of the input numbers are equally likely
– On a random input list, we expect a mix of well-balanced and
unbalanced splits
– Good and bad splits are randomly distributed across the tree
1
n
n-1
(n – 1)/2
combined cost:
2n-1 = (n)
(n – 1)/2
n
(n – 1)/2 + 1
Alternate of a bad
and a good split
combined cost:
n = (n)
(n – 1)/2
Nearly wellbalanced split
• Running time of quick-sort when levels alternate
between good and bad splits is O(n log n)
Introduction to Computer Science I: T7
55
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Performance of Quick Sort
• Typically, quick-sort is faster in practice than other
Θ(n log n) algorithms
– Its inner loop can be efficiently implemented on most
architectures
– In most real-world data, it is possible to make design choices
which minimize the possibility of requiring quadratic time
Introduction to Computer Science I: T7
56
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Summary of Cost of Computations
• Algorithms can be classified according to their
complexity  O-Notation
– only relevant for large input sizes
• "Measurements" are machine independent
– counting operations in terms of the input size
– worst-, average-, best-case analysis
• Algorithms strongly vary in their efficiency
– Good programming  one or two complexity classes less
– Some problems are inherently complex
Introduction to Computer Science I: T7
57
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Outline
•
•
•
•
Abstract time for complexity analysis
O-Notation and other notations for asymptotic growth
Techniques for measuring algorithm complexity
Vectors in Scheme
Introduction to Computer Science I: T7
58
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Cost of Lookup in List
Recall the example of finding a route in a graph:
(define (find-route origin destination G)
(cond
[(symbol=? origin destination)
(list destination)]
[else
(local ((define possible-route
(find-route/list
(neighbors origin G)
destination
G)))
(cond
[(boolean? possible-route) false]
[else (cons origin possible-route)]))]))
Introduction to Computer Science I: T7
59
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Cost of Lookup in List
;; neighbors : node graph -> (listof node)
;; to lookup the node in graph
(define (neighbors node graph)
(cond
[(empty? graph) (error “no neighbors")]
[(symbol=? (first (first graph)) node)
(second (first graph))]
[else (neighbors node (rest graph))]))
neighbors is similar to contains-doll?
i.e. neighbors is O(n)
Introduction to Computer Science I: T7
60
Cost of Lookup in List
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
The complexity of
neighbors is O(n)
neighbors is used
at every stage of
find-route,
i.e. n times in case
of maximal route
the algorithm requires
O(n2) steps in
neighbors
neighbors can be the
bottleneck of find-route!
• We need a data structure that allows the access to
the neighbors of a given node by name within
constant time
• Vectors are data structures which allow element
access in constant time.
Introduction to Computer Science I: T7
61
Operations on Vectors
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
• vector creates a new vector from given values:
(vector V-0 ... V-n)
• build-vector is essentially the same as build-list:
(build-vector n f)
= (vector (f 0) ... (f (- n 1)))
• vector-ref extracts a value from the vector
(vector-ref (vector V-0 ... V-n) i) = V-i, 0 ≤ i ≤ n
• vector-length returns the number of elements:
(vector-length (vector V-0 ... V-n)) = (+ n 1)
• vector? is the vector predicate:
(vector? (vector V-0 ... V-n)) = true
(vector? U) = false
Introduction to Computer Science I: T7
62
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
Graphs as Vectors
©
Nodes can be represented by numbers:
List-based representation:
(define
'((A
(B
(C
(D
(E
(F
(G
Graph-as-list
(B E))
(E F))
(D))
())
(C F))
(D G))
())))
A
B
C
D
E
F
G
0
1
2
3
4
5
6
Vector-based representation:
(define Graph-as-vector
(vector (list 1 4)
(list 4 5)
(list 3)
empty
(list 2 5)
(list 3 6)
empty))
The vector's i-th field contains the list of
neighbors of the i-th node
Introduction to Computer Science I: T7
63
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Graphs as Vectors
• A node is a
natural number between 0
and n – 1, where n is
the number of nodes
• A graph is a vector of nodes:
A
B
C
D
E
F
G
0
1
2
3
4
5
6
(vectorof (listof node))
• Now, neighbors can be executed for a node in constant
time
=> If we look at the abstract time measurement of find-route,
this can be ignored.
;; neighbors : node graph -> (listof node)
;; to lookup the node in graph
(define (neighbors node graph)
(vector-ref graph node))
Introduction to Computer Science I: T7
64
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Graphs as Vectors
• Now neighbors of a node is a constant-time
operation
=> We can ignore it when we study the abstract running
time of find-route.
;; neighbors : node graph -> (listof node)
;; to lookup the node in graph
(define (neighbors node graph)
(vector-ref graph node))
Introduction to Computer Science I: T7
65
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Processing Vectors
Programming with vectors means programming with
vector-ref – thinking about vectors and indices into them
Example: The function vector-sum-for-3 uses vectors of three
numbers and returns their sum:
;; (vector number number number)
(define (vector-sum-for-3 v)
(+ (vector-ref v 0)
(vector-ref v 1)
(vector-ref v 2)))
Introduction to Computer Science I: T7
->
number
66
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Processing Vectors
Consider the more general function vector-sum that
works with vectors of arbitrary size:
;; vector-sum : (vectorof number)
;; to sum up the numbers in v
(define (vector-sum v) ...)
->
number
Here are some examples:
(= 0 (vector-sum (vector -1 3/4 1/4)))
(= 1 (vector-sum (vector .1 .1 .1 .1 .1 .1 .1 .1 .1 .1))
(= 0 (vector-sum (vector)))
Introduction to Computer Science I: T7
67
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Processing Vectors
vector-sum does not receive the length of vector – the
number of elements to be processed.
We must define an auxiliary function with such an
argument:
;; vector-sum-aux:(vectorof number) n -> number
;; to sum up the numbers in v relative to i
(define (vector-sum-aux v i) ...)
Then vector-sum is as follows:
(define (vector-sum v)
(vector-sum-aux v (vector-length v)))
Introduction to Computer Science I: T7
68
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Processing Vectors
First, we develop a template for the function.
Implementation of vector-sum-for-3 suggests that i
is the varying argument in the template.
;; (vectorof number) n -> number
;; to sum up the numbers in v with index in [0, i)
(define (vector-sum-aux v i)
(cond
[(zero? i) ...]
[else ... (vector-sum-aux v (pred i)) ...]))
The template suggests that we should consider i as the
number of items of v that vector-sum-aux must
consider.
Introduction to Computer Science I: T7
69
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Processing Vectors
1. If i is 0, there are no further items to be considered
=>The result is 0.
2. Otherwise,
– Compute the sum of the numbers in v with indices less than
i-1:
(vector-sum-aux v (pred i))
– Take the value of vector field with index i-1:
(vector-ref v (pred i))
 the result is their sum:
(+ (vector-ref v (pred i))
(vector-sum-aux v (pred i))
Introduction to Computer Science I: T7
70
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Processing Vectors
;; (vectorof number) -> number
;; to compute the sum of the numbers in v
(define (vector-sum v)
(vector-sum-aux v (vector-length v)))
;; (vectorof number) n -> number
;; to sum the numbers in v with index in [0, i)
(define (vector-sum-aux v i)
(cond
[(zero? i) 0]
[else (+ (vector-ref v (pred i))
(vector-sum-aux v (pred i)))]))
vector-sum-aux extracts the numbers from the
vector in a right-to-left order as i decreases to 0
Introduction to Computer Science I: T7
71
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Processing Vectors
The sum can also be computed from left to right:
;; lr-vector-sum : (vectorof number)
;; to sum up the numbers in v
(define (lr-vector-sum v)
(vector-sum-aux v 0))
->
number
;; vector-sum : (vectorof number) -> number
;; to sum up the numbers in v with index in
;; [i, (vector-length v))
(define (vector-sum-aux v i)
(cond
[(= i (vector-length v)) 0]
[else (+ (vector-ref v i)
(vector-sum-aux v (succ i)))]))
Introduction to Computer Science I: T7
72
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Creating Vectors
• On the next slides, we will briefly examine
how to create vectors
• To illustrate this, we develop a function that
moves the elements of a given vector at a
given velocity.
Introduction to Computer Science I: T7
73
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Building Vectors
The velocity of an object can be represented by a vector:
– (vector 1 2) – the velocity of an object on a plane that
moves 1 unit to the right and 2 down in each time unit.
– (vector -1 2 1) – velocity in space; -1 units in the x
direction, 2 units in the y direction, and 1 units in the z
direction.
Let us develop a function that computes the
displacement for an object with some velocity v in t
time units:
;; (vectorof number) number -> (vectorof number)
;; to compute the displacement of v and t
(define (displacement v t) ...)
Introduction to Computer Science I: T7
74
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Building Vectors
Some examples:
(equal? (displacement (vector 1 2) 3)
(vector 3 6))
(equal? (displacement (vector -1 2 1) 6)
(vector -6 12 6))
(equal? (displacement (vector -1 -2) 2)
(vector -2 -4))
To compute the result, we just multiply each dimension
of the velocity vector with the number representing the
time and return a new vector.
Introduction to Computer Science I: T7
75
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Building Vectors
We construct a vector of the same length as v:
(build-vector (vector-length v) ...)
Now we need to replace ... with a function that computes
the 0-th, 1-st, and so on items of the new vector:
;; new-item : n -> number
(define (new-item index) ...)
Then we multiply (vector-ref v i) with t and that's it:
;; (vectorof number) number -> (vectorof number)
;; to compute the displacement of v and t
(define (displacement v t)
(local ((define (new-item i)
(* (vector-ref v i) t)))
(build-vector (vector-length v) new-item)))
Introduction to Computer Science I: T7
76
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Building Vectors
Since the local function new-item is not recursive, we
can replace it with a lambda expression:
;; (vectorof number) number -> (vectorof number)
;; to compute the displacement of v and t
(define (displacement v t)
(build-vector (vector-length v)
(lambda (i) (* (vector-ref v i) t))))
In mathematics, this function is called scalar product…
This and many other mathematical operations with
vectors can be naturally expressed in Scheme.
Introduction to Computer Science I: T7
77