程序代写代做代考 algorithm Algorithm Design & Analysis: Efficiency & Complexity

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