Algorithm Design & Analysis: Efficiency & Complexity
Overview
Algorithm Design & Analysis
Motivation
Efficiency and Space complexity Efficiency: Time complexity
Of algorithms
Of problems
Conclusions and lessons
Slide #2 of 39
Motivation
We want to build computer systems that work
• And that work well!
To do this we need to think about several factors: • They must give the correct answer
• Is this ALWAYS true?
• They must be reliable, maintainable, quick to produce, cheap …
• Again, is this always true?
• They must be usable – by the user of the system
• They must be efficient
Slide #3 of 39
Efficient?
We want our software to:
• Run as quickly as possible
• Respond as quickly as possible
• Use as little memory as possible
• Use as little network bandwidth as possible
• Use as little power as possible
• …….
Slide #4 of 39
Efficient?
So, we are actually trying to optimise many things: • The balance will depend on our problem
One serious issue we need to consider is:
• Our solution may work very well for ‘small’ problems
• But, if the problem gets more complex how does its performance change?
• Does it get worse?
• Does it get MUCH worse?
• Does it get MUCH, MUCH worse?
Slide #5 of 39
What are we interested in?
Actually, there are several things to consider:
• Is our implementation of our algorithm or data
representation efficient:
• Could we improve our code to make it run faster?
• This might speed things up a bit
• or a lot … maybe 10 or 100 times
• Could we improve our data representation so it uses less memory?
• Again we might improve things dramatically
• But what if our algorithm is inherently going to perform worse as
the amount of data increases?
• What if our problem is inherently hard and gets much harder as
the size of the problem grows?
Slide #6 of 39
So?
We need to understand how our problem and/or algorithm changes in complexity as it gets larger.
Usually, we focus more on time complexity – how much computation is involved in solving a problem:
• For instance, if we double the size of our problem
(e.g. twice as much data) then what happens to the
computation time:
• Does it stay the same?
• Does it get a bit harder? Maybe +30%
• Does it get a lot harder? Maybe +100%
• Does it get even worse? Maybe +400% or +800% or worse?
• Usually, we are interested in an almost qualitative measure
Slide #7 of 39
Space complexity
Usually, space (or bandwidth) complexity is not
considered in the same way as computational
complexity:
• Memory and bandwidth are limited by practical constraints
• We can add memory (and bandwidth or processing) to cope with
a bigger problem
• We can constrain our problem to the practical constraints
• We restrict the resolution of videos to what is practical
• We restrict the resolution of 3D models to what is practical
• We can use other techniques to reduce the memory
demands (e.g. compression or streaming)
Slide #8 of 39
An Example: video
Typical HD video:
• 1920×1080 pixels (4 bytes per pixel):
• ~2MPixels, ~8Mbytes
• 25 frames per second • 200 Mbytes/sec
Solution:
• Compression (up to 200:1)
• Using empirical knowledge of human vision & video streams
• Lossy compression (cf. lossless compression)
• Reduce frame rate or resolution
• Constrained by practical constraints
Slide #9 of 39
How does the problem change with resolution?
If we double the resolution of a 2D image
• We x4 the number of pixels – n2
• If we have a 3D image (e.g. from an MRI scanner)
• If we double the resolution then: x8 – n3
The same problem will occur with 2D models and will be even worse as the number of dimensions increases:
• n2,n3….
Slide #10 of 39
Time complexity
To develop a basic understanding
of algorithm design and efficiency in terms of worst case time complexity.
Slide #11 of 39
Outline / Topics
Algorithm Design and Analysis Efficiency
Time Complexity
Big-O Notation
Examples Lessons
Slide #12 of 39
What is an Algorithm?
In mathematics, computer science, and related subjects, an algorithm is an effective method for solving a problem expressed as a finite sequence of instructions.
o
Abu Abdullah Muhammad bin Musa Al-Khwarizmi
a Muslim mathematician
invented algorithms to solve quadratic equations
the word algorithm derived from his Latin name Algorithmi
An even earlier algorithm is the sieve of Eratosthenes
o
o o o
Slide #13 of 39
Algorithm: question?
Which one is an algorithm?
A recipe for making tomato soup?
A procedure to sort 1000 numbers into ascending numeric order?
A procedure to recognize a particular face in a crowd? A method to order objects according to beauty?
Slide #14 of 39
Algorithm Design and Analysis
Multiple algorithms often exist for the same task: All of them give correct results
How do we select the best one?
Many possible (and often conflicting) criteria: Efficiency
?
simplicity, clarity
elegance, proofs of correctness
We need to ask
is my algorithm correct?
does my algorithm always terminate? does an algorithm even exist?
Slide #15 of 39
Algorithm Efficiency
Resource usage of an algorithm
typically: time (runtime) and space (computer memory) also: network usage, hardware requirements, …
…… consider trade-offs between resources
How do we measure the run-time of an algorithm? benchmarking on representative set of inputs: empirical
analysis
analyse the (time) complexity
Slide #16 of 39
Algorithm Efficiency – Empirical Analysis
Idea: Implement the algorithm (a program) and time it
Question: How can we time a program? Manual: Using stopwatch
Automatic: Using some timer function
Run the program for various input sizes and measure run time.
Slide #17 of 39
Algorithm Efficiency – Time Complexity
Time complexity:
the number of operations that an algorithm requires to execute,
in terms of the size of the input or problem Note:
algorithm, not implementation
so: pseudocode; no fixed programming language, computer
architecture ……
“in terms of” – complexity defined as a function T(n)
Questions:
what do we mean by operations?
what do we mean by size?
we usually focus on worst-case, not average-case, analysis
Slide #18 of 39
Example # 1
Look up a value v in an array x of integers
Algorithm: Linear Search
inputs: array x of size n, integer v
return: index of first occurrence of v in x, or -1 if none
T(n) = n
Slide #19 of 39
Example # 2
Matrix-Vector Multiplication: x = A b n x n matrix A, vector of b size n
Algorithm
inputs: matrix A, vector b
result stored in vector x (initially all 0)
T(n) = 2n2
Slide #20 of 39
Quadratic Growth
Consider the two functions f(n) = n2
g(n) = n2 – 3n + 2 Around n = 3, they look very different
Slide #21 of 39
Quadratic Growth
Around n = 10, they look similar
Slide #22 of 39
Quadratic Growth
Around n = 100, they are almost the same
Slide #23 of 39
Quadratic Growth
Around n = 1000, the difference is indistinguishable!
Slide #24 of 39
Quadratic Growth
The absolute difference is large, such that, f(1000) = 1000000
g(1000) = 997002 but the relative difference is very small,
and this difference goes to zero as n → ∞
Slide #25 of 39
Big-O Notation
Usually we don’t need exact complexity T(n) it suffices to know the complexity class
we ignore constant factors/overheads, lower orders focus on performance for large n (“asymptotic”)
Big-O notation
for example: O(n2) “O of n squared” “on the order of n2”
Examples
T(n) = n ⟹ complexity class = O(n)
T(n) = n+2 ⟹ complexity class = O(n) T(n) = 2n2 ⟹ complexity class = O(n2)
Slide #26 of 39
Big-O Notation
More Examples
T(n) = 10n3 + 1 ⟹ complexity class = O(n3) T(n) = 5(n+2) ⟹ complexity class = O(n)
T(n) = 1000 ⟹ complexity class = O(1) T(n) = n2 + n + 1 ⟹ complexity class = O(n2)
Determining the complexity class
intuitively, it suffices to count the number of loops and the number of times they are executed
Slide #27 of 39
Big-O Notation: Common Complexity Classes
Some common complexity classes: O(1) = “Constant”
O(log2 n) = “Logarithmic”
O(n) = “Linear”
O(n log2 n) = “Log Linear” O(n2) = “Quadratic” O(n3) = “Cubic”
O(2n) = “Exponential”
Polynomial: O(n), O(n2), O(n3), … – “tractable” Exponential: O(2n), O(Cn), – “intractable”
Slide #28 of 39
Some concrete numbers …
How many operations needed for an algorithm? with complexity T(n) = f(n) and input size n
Slide #29 of 39
Some concrete numbers …
How much time needed for an algorithm? assuming 1 million operations per second
Slide #30 of 39
Graphically
Slide #31 of 39
Example # 1 (again)
Look up a value v in an array x
Slide #32 of 39
Example # 1 (again)
Look up a value v in a sorted array x
Slide #33 of 39
Example # 1 (again)
Look up a value v in a sorted array x
Algorithm: Binary Search inputs: sorted array x of size n,
integer v
return: index of first occurrence of
v in x, or -1 if none
Complexity = O(log2n)
Slide #34 of 39
Computing Complexity Classes
Determine total algorithm complexity from the complexities of its components
1) Sequential algorithm phases 2) Function / Method calls
Slide #35 of 39
Sequential Algorithm Phases
Example: matrix-vector multiplication: x = A b matrix-vector multiplication x = A b initialise vector x (all 0), then add values to x
Complexity: O(n) + O(n2) = O(n2) In general: “maximum” of complexities
Slide #36 of 39
Function/Method calls
Example: n array look-ups
Complexity: O(n) x O(log n) = O(n log n) In general: “multiplication” of complexities
Slide #37 of 39
Computing Complexity Classes
Determine total algorithm complexity from the complexities of its components
1) Sequential algorithm phases: “maximum” e.g. O(n) + O(n2) = O(n2)
e.g. O(n) + O(log n) = O(n)
2) Function / Method calls: “multiplication” e.g. O(n) x O(log n) = O(n log n)
e.g. O(n2) x O(1) = O(n2)
Slide #38 of 39
Question # 1
Given the following code fragment, what is its Big-O running time?
a) O(n)
b) O(n2)
c) O(log n) d) O(n3)
Slide #39 of 39
Question # 2
Given the following code fragment, what is its Big-O running time?
a) O(n)
b) O(n2)
c) O(log n) d) O(n3)
Slide #40 of 39
Question # 3
Given the following code fragment, what is its Big-O running time?
a) O(n)
b) O(n2)
c) O(log n) d) O(n3)
Slide #41 of 39
Some Harder Problems
Traveling Salesman Problem (TSP)
given n cities and the distances between them, what is the shortest possible route that visits each city exactly once and then returns to the first city?
https://en.wikipedia.org/wiki/Travelling_salesman_problem https://www.youtube.com/watch?v=SC5CX8drAtU
Slide #42 of 39
Some Harder Problems
Boolean Satisfiability Problem (SAT)
Given a Boolean formula F(x1, x2, x3, …, xn)
Can F evaluate to 1 (true)?
If yes, return values of xi’s (satisfying the assignment) that make F true.
In both cases (TSP & SAT):
lots of practical applications (Operations Research, Optimization, Logistics, Model Checking, Software Verification, … etc.)
also important problems in theoretical computer science
Slide #43 of 39
Algorithms vs. Problems
Algorithm complexity
worst-case run-time of algorithm – “efficiency”
actually an upper bound: algorithm A is in O(f(n)) if the worst-case run-time is at most f(n)
usually use tightest (most informative) complexity Problem complexity
complexity class = set of problems
problem X is in complexity class O(f(n)) if there exists an
algorithm to solve it in O(f(n)) – “difficulty”
again: this is an upper bound (and uses the tightest
possible)
sometimes consider lower bounds: e.g. sorting: O(n log n)
Slide #44 of 39
P and NP
Complexity classes
O(1) ⊆ O(log n) ⊆ O(n) ⊆ O(n log n) ⊆ O(n2) ⊆ O(2n)
polynomial time (PTIME or P) – assumed to be “tractable”
Another famous class: NP
if we can “guess” a solution, it can be checked efficiently
(efficiently = in polynomial time)
NP-hard problems
e.g. travelling salesman problem, SAT, …
only exponential time algorithms are known
but some efficient heuristics exist in practice P = NP?
Nobody knows … US$1,000,000 prize if you solve it!
Slide #45 of 39
Summary
Algorithm design and analysis: Efficiency
Time Complexity
(worst-case) number of operations an algorithm needs to
execute, in terms of the size of the input or problem: T(n)
Big-O notation
complexity classes: O(n), O(n log n), O(2n), … focus on large values of n (i.e. asymptotic behaviour) ignore constants, lower factors
count loops/iterations, decompose algorithm complexities for algorithms/problems
Slide #46 of 39
Summary & Lessons
Data Representation/Algorithms are tightly linked Some algorithms are just better than others:
But sometimes the ‘best’ depends on the problem Some problems are inherently hard (in the complexity
sense)
This doesn’t mean they cannot be solved We may need to reformulate the problem
Constrain it
Relax conditions
E.g. instead of “find the best ….” we “find a very good ….”
Slide #47 of 39