Ch3. Asymptotic Notation

31  Download (0)

전체 글

(1)

Ch3. Asymptotic Notation

© copyright 2006 SNU IDB Lab.

(2)

Preview of Chapters



Chapter 2

 How to analyze the space and time complexities of program



Chapter 3

 Review asymptotic notations such as O, Ω, Θ, o for simplifying the analysis



Chapter 4

 Show how to measure the actual run time of a program by using a clocking method

(3)

Bird’s eye view



In this chapter

 We review asymptotic notations: O, Ω, Θ, o

 The notations are for making statement about program performance when the input data is large

 Big-Oh “O” is the most popular asymptotic notation

 Asymptotic notations will be introduced in both informal and rigorous manner

(4)

Table of Contents



Introduction



Asymptotic Notation & Mathematics



Complexity Analysis Example



Practical Complexities

(5)

Introduction (1/3)

 Reasons to determine operation count and step count

 To predict the growth in run time

 To compare the time complexities of two programs

 Facts of the previous two approaches

 The operation count method ignores all others except key operations

 The step count method overcome the above shortage, but the notion of step is inexact

 x=y and x=y+z+(y/z) treated as a same step?

 Two analysts may arrive at 4n + 3 and 900n + 4 for the same program

 Asymptotic analysis focuses on determining the biggest terms (but not their coefficient) in the complexity function.

(6)

Introduction (2/3)

 If the step count is , coefficients and n term cannot give any particular meanings when the instance size is large

 Let n1 and n2 be two large values of the instance size

 We can conclude that if the instance size is doubled, the runtime increases by a factor of 4

3 2

2

1n c n c

c + +

3 2

2

1

n c n c

c + +

0 )

( 2

1 3 1

lim

2 + =

c n

c n

c c

n

c1 is dominant factor when n is large

large!

very is

n when important

2

is

1

n

c

2 2 1 2

2 1

2 1 1 2

1 ( )

) (

) (

n n n

c n c n

t n

t = =

(7)

Introduction (3/3)

• Program A

• Program B

n n

n

n 3 or 3

2

2

+

2

+

n n or 43 83

When n is large, program B

is faster than program A

(8)

Table of Contents



Introduction



Asymptotic Notation & Mathematics



Complexity Analysis Example



Practical Complexities

(9)

Asymptotic Notation: concepts



Definition

 p(n) is asymptotically bigger than q(n)

 q(n) is asymptotically smaller than p(n)

 p(n) and q(n) is asymptotically equal iff neither is asymptotically bigger than the other

) 0 (

)

lim ( =

p n n q

n

(10)

Asymptotic Notation: terms



Commonly occurring terms

! 2

log log

1 < n < n < n n < n

2

< n

3

<

n

< n

(11)

Asymptotic Notation: Big Oh

 f(n) is big oh of g(n)

 The above notation means that f(n) is asymptotically smaller than or equal to g(n)

 g(n), multiplied by some constant C gives an asymptotic upper bound for f(n)



The notation gives no clue to the value of this constant C, it only states that it exists

)) (

( )

( n O g n

f = lim ( ( ) ) = 0 or Constant C

g n n f

n

(12)

Big Oh arithmetic



Definition

 Consider f(n) = 3n+2

 When then f(n) <= 4n

 f(n) = O(n), therefore g(n) = n

 f(n) is bounded above by some function g(n) at all points to the right of

0 0

all for )

( )

( such that exist

n and c

constants positive

iff )) ( ( )

(

n n, n

n cg n

f n g O n

f

=

2 ,

4

0

=

= n c

n

0

(13)

)) ( ( )

(n O g n

f =

(14)

Big Oh example

3 3

3 2

0

3 2

7 4

3 4

3

0 ,

7

) ( 4

3 )

(

n n

n n

n

n c

n n

n n

f

= +

≤ +

=

=

Ο

= +

=

n n

n n

n n

n n

n

n c

n n

n n

f

4 3

4 4

4

4 4

3

4 ,

4

) ( 4

3 ) (

2 2

2 2 2

0

2 2

+

≤ +

=

=

Ο

= +

=

Θ

Big O gives us an upper bound,

but does not promise a careful

(tight) upper bound!!!

(15)

Asymptotic Notation: Big Theta



Theta(Θ) Notations



f(n) is theta of g(n)



f(n) is asymptotically equal to g(n)



g(n) is an asymptotic tight bound for f(n)

)) (

( )

( n g n

f = Θ

c1

lim

gf ((nn)) c2

n

(16)

Big Theta



Definition



f(n) is bounded above and below by some function g(n) at all points to the right of

0 2

2 2

0 2

1

2 2

all for 7n

4n 3n

3 have we

0 n

and 7

c 3, c

choose :

Proof

) ( 4

3 :

n n, n

n

n n

n Example

≤ +

=

=

=

Θ

= +

0 2

1

0 2

1

all for ) ( )

( )

( such that

exist n

an and c

and c

constants positive

iff ))

( ( )

(

n n, n

n g c n

f n

g c

n g n

f

≤ Θ

=

n

0

(17)

) ( )

( )

(

iff ))

( ( )

( n g n c

1

g n f n c

2

g n

f = Θ ≤ ≤

(18)

Big Theta arithmetic

 Example

2 1

that such

2 1

) 0 (

4 1

2 3

3

2 1

, 4 ,

3

) (

) (

, 1 2

3 )

(

0 2 2

2

0 2

1

2 2

+

= +

>

≤ +

+

+

=

=

=

Θ

= +

+

=

n n

n n

n n

n

n c

c when

n n

f n

n n

f

(19)

Asymptotic Notation: Big Omega



Omega(Ω) Notations



f(n) is omega of g(n)



f(n) is asymptotically bigger than or equal to g(n)



g(n) is an asymptotic lower bound for f(n)



It is the reverse of big-O notation

)) (

( )

( n g n

f = Ω lim ( ( ) ) = or Const.

g n n f

n

(20)

Big Omega arithmetic



Definition



f(n)=3n+2 > 3n for all n, So

 f(n) is bounded below by a function g(n) at all points to the right of

0 0

all for

) ( )

( such that exist

n and c

constants positive

iff )) ( ( )

(

n n, n

n cg n

f n

g n

f

≥ Ω

=

) ( )

( n n

f = Ω

n

0

(21)

) ( )

( iff )) ( ( )

( n g n f n cg n

f = Ω ≥

(22)

Little Oh Notation (o)



Definition



Upper bound that is not asymptotically tight



Example

)) ( ( )

(

)) ( ( )

( iff )) (

( )

( n o g n f n O g n and f n g n

f = = ≠ Ω

) ( 2

3

) ( 2

3 as ) ( 2

3 n + = o n

2

n + = O n

2

and n + ≠ Ω n

2

(23)

Big oh and Little oh



Big O notation may or may not be asymptotically tight



We use little o notation to denote an upper bound that is not asymptotically tight

not tight :

) (

2 . tight vs :

) (

2 n

2

= O n

2

n = O n

2

) (

2 )

( 2

: n o n

2

n

2

o n

2

Ex = ≠

(24)

Legend in Asymptotic Notation



Roughly f(n) = g(n) means f(n) = g(n)



Roughly f(n) = g(n) means f(n) <= g(n)



In general we use even though we get !



In fact, is a kind of



Another reason: In general, finding is difficult!



Our textbook will use and interchangeably!

Ο Θ

Ο Θ

Ο Θ Θ

Θ Ο

(25)

Table of Contents



Introduction



Asymptotic Notation & Mathematics



Complexity Analysis Example



Practical Complexities

(26)

Sequential Search

 Expression of step count as an asymptotic notation (program 2.1)

 Ignore terms without n!

n is bound upper

) ( )

( case

Worst

1 is bound lower

) 1 ( )

(

case Best

==>

=

==>

=

n O n

t

n t

Search sequential

Search sequential

(27)

Binary Search

public static int binarySearch(Comparable [] a, Comparable x) {// Search a[0] <= a[1] <= ... <= a[a.length-1] for x.

int left = 0;

int right = a.length - 1;

while (left <= right)

{ int middle = (left + right)/2;

if (x.equals(a[middle]) return middle;

if (x.compareTo(a[middle]) > 0) left = middle + 1;

else right = middle - 1;

}

return -1; // x not found }

• Each iteration of the while loop  Decrease in search space by a factor about 2

Best case complexity 

• Worst case complexity  Θ(log a.length) // because we have to go down to leaf nodes!

Example 3.24

) 1 (

(28)

Table of Contents



Introduction



Asymptotic Notation & Mathematics



Complexity Analysis Example



Practical Complexities

(29)

Practical Complexities



1,000,000,00 instructions per second computer



To execute a program of complexity f(n)

(30)

Summary



Big-O  upper bound



Big-theta  tight (upper & lower) bound



Big-omega  lower bound

) (

) (

Ω(n) n

) (

) (

) (

) (

) (

) (

3 2

2 2

2

3 2

2 2

2

3 2

2 2

2

n n

n n

n n

n n

n n

n n

n n

n n

≠ Ω

=

=

Θ

≠ Θ

= Θ

Ο

= Ο

= Ο

(31)

Summary



In this chapter

 We reviewed asymptotic notation O, Ω, Θ, o

 Asymptotic notation is for making statement about program performance when the input data is large

 Big O notation is the most popular asymptotic notation

 Asymptotic notations were introduced in both informal and rigorous manner

수치

Updating...

참조

관련 주제 :