CS计算机代考程序代写 algorithm PowerPoint Presentation

PowerPoint Presentation

Algorithm Design & Analysis: Efficiency & Complexity

Slide #2 of 39

Overview

Algorithm Design & Analysis

 Motivation

 Efficiency and Space complexity

 Efficiency: Time complexity

 Of algorithms

 Of problems

 Conclusions and lessons

Slide #3 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 #4 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 #5 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 #6 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 #7 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 #8 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 #9 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 #10 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 #11 of 39

Time complexity

To develop a basic understanding

of algorithm design and efficiency in terms of

worst case time complexity.

Slide #12 of 39

Outline / Topics

 Algorithm Design and Analysis

 Efficiency

 Time Complexity

 Big-O Notation

 Examples

 Lessons

Slide #13 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 Muhammad bin -Khwarizmi

o a Muslim mathematician

o invented algorithms to solve quadratic equations

o the word algorithm derived from his Latin name

Algorithmi

o An even earlier algorithm is the sieve of Eratosthenes

Slide #14 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 #15 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 #16 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 #17 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 #18 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 #19 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 #20 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 #21 of 39

Quadratic Growth

Consider the two functions

f(n) = n2

g(n) = n2 – 3n + 2

Around n = 3, they look very different

Slide #22 of 39

Quadratic Growth

Around n = 10, they look similar

Slide #23 of 39

Quadratic Growth

Around n = 100, they are almost the same

Slide #24 of 39

Quadratic Growth

Around n = 1000, the difference is indistinguishable!

Slide #25 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 #26 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 #27 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 #28 of 39

Big-O Notation: Common Complexity Classes

 Some common complexity classes:

O(1) = “Constant”

O(log
2

n) = “Logarithmic”

O(n) = “Linear”

O(n log
2

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 #29 of 39

Some concrete numbers …

 How many operations needed for an algorithm?

with complexity T(n) = f(n) and input size n

Slide #30 of 39

Some concrete numbers …

 How much time needed for an algorithm?

 assuming 1 million operations per second

Slide #31 of 39

Graphically

Slide #32 of 39

Example # 1 (again)

 Look up a value v in an array x

Slide #33 of 39

Example # 1 (again)

 Look up a value v in a sorted array x

Slide #34 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(log
2
n)

Slide #35 of 39

Computing Complexity Classes

 Determine total algorithm complexity

 from the complexities of its components

1) Sequential algorithm phases

2) Function / Method calls

Slide #36 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 #37 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 #38 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 #39 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 #40 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 #41 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 #42 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://en.wikipedia.org/wiki/Travelling_salesman_problem

Slide #43 of 39

Some Harder Problems

 Boolean Satisfiability Problem (SAT)

Given a Boolean formula F(x
1
, x

2
, x

3
, …, x

n
)

Can F evaluate to 1 (true)?

 If yes, return values of x
i
’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 #44 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 #45 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!

https://en.wikipedia.org/wiki/Millennium_Prize_Problems

Slide #46 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 #47 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 ….”