Tempo di calcolo

(1)

Ugo de’ Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 3

Tempo di calcolo

Introduzione alla complessità computazionale concreta

Quale algoritmo è più veloce?

Ci interessa rispondere:

• per capire quanto tempo ci vuole per eseguire un programma che lo implementa

• per stimare la grandezza massima

dell’ingresso di un’esecuzione ragionevole

• per confrontare l’efficienza di più algoritmi che risolvono lo stesso problema

• per sapere quale parte del codice sarà eseguita più volte ...

Altre misure oltre il tempo

• VSD]LR = quanta memoria occorre per eseguire l’algoritmo

• KDUGZDUH = numero di processori, numero

dei componenti (porte) di un circuito, ecc...

(2)

Il tempo di calcolo è una funzione

Programma

ingresso/istanza uscita/risposta

Quanto tempo impiega?

dipende dall’ ingresso

Definizione del tempo

Calcoliamo:

• il numero dei secondi (dipendente dalla macchina)

• il numero delle operazioni elementari, ciascuna con un proprio coefficiente

• il numero delle volte che una specifica operazione viene eseguita

Sotto certe condizioni queste misure differiscono di un fattore

costante!

Esempio: minimo in un vettore

costo volte

(, , ) 1 1

Pre: vettore di dimensione > ≥ Post: ritorna il minimo in [..]

←[] ₂ 1

← + 1 3 − 1

[] < ₄ −

←[] 5 ≤ −

6 1

!

"#$%%&('*)+

%,.-

-/

0

-

0

(3)

Esempio: minimo in un vettore

Posto = − + 1, vale a dire il numero degli elementi tra i quali cerchiamo il minimo, si ha

1

243

5

2 5525525255

5 55252255

5

2

6

7

+

=

+

−

− + + + +

=

+

− +

− + + +

=

+

− +

− + + +

≤

) (

) 1 ( ) 1 ( )

, (

6 5 4 2 1 5 4 3

6 5 5 4 4 3 2 1

6 5 4 3 2 1

con ⁸ e ⁹ costanti.

La dimensione dell’ ingresso

•

Nel caso di

^:<;^=>;^?A@

(

^B

,

^C

,

^D

) ciò che conta è il numero degli elementi in

^B

[

^C

..

^D

], non il loro valore

•

In generale la dimensione dell’ ingresso è una

misura della sua rappresentazione

(a meno di una costante)

|^.E = dimensione di

= num. bit per rappresentare ^GF log2( + 1) 

| [0.. −1] | = dimensione di [0.. −1]

= , dove = num. bit del generico el. di []

Quale ingresso di dimensione Q?

Supponiamo di voler esprimere

^H

in funzione della dimensione dell’ istanza, invece che dell’ istanza stessa:

|^I| = |^J | non implica ^K (^I ) = ^K(^J )

Come definire ^K sulla dimensione?

(4)

Quale ingresso di dimensione Q?

Supponiamo di voler esprimere

^H

in funzione della dimensione dell’ istanza, invece che dell’ istanza stessa:

Distinguiamo allora i casi

caso migliore: Î t.c. ^K migliore(|Î|) = ^K(Î)

}

|

| : ) ( min{

)

migliore

( Q 7 [ [ Q

7 = =

(, , ): quando il minimo è[]

Quale ingresso di dimensione Q?

Supponiamo di voler esprimere

^H

in funzione della dimensione dell’ istanza, invece che dell’ istanza stessa:

Distinguiamo allora i casi

caso peggiore: Î t.c. ^K peggiore(|Î |) = ^K(Î)

}

|

| : ) ( max{

)

peggiore

( Q 7 [ [ Q

7 = =

(, , ): quando [..] è ordinato in senso decrescente

Quale ingresso di dimensione Q?

istanze in input 5 ms

3 ms

1 ms

A B C D E F G

tempo nel caso peggiore

tempo nel caso migliore

In questo grafico non vi è alcun ordine sulle istanze

(5)

Quale ingresso di dimensione Q?

Come potremmo definire un caso

“tipico”, o medio?

“medio” vuol dire

“valore atteso di una variabile casuale”

Il caso medio

L = spazio campione

s ∈^L evento elementare

A ⊆ S evento 0

1

Pr

Pr distribuzione di probabilitàse

∑

∈

= ^M

NPO

Q )Pr()

Pr(

1 ) Pr(

)

Pr( =

∑

_∈ =

R

SUT

V

Il caso medio

WW

X

variabile casuale

∑

₌

∈

=

∈

=

= ^Y

Z

[

\

Z ]

^

]

_

`

]

^

_

) ( ,

) Pr(

} ) ( : Pr{

} Pr{

S = spazio campione

distr. prob. quando ^X vale^I

(6)

Il caso medio

Ogni variabile casuale ^X su ^L definisce un nuovo spazio

} Pr{

) Pr(

}, , ) ( : { )

( 6 [ ; V [ V 6 [ ; [

; = = ∈ = =

i cui eventi elementari sono i valori di ^a .

∈

∑

=

) (

} Pr{

b

c

d

[

; Valore attesodi [

a rispetto a Pr

evento “^a (^e) = ^f” verosimiglianza dell’ evento

Il caso medio

Per definire ^gmedia(^h) poniamo:

1. ⁱ = insieme delle istanze di dimensione ^h 2. â (ê) = ^g (ê) dove |ê| = ^h

3. una distribuzione di probabilità Pr su ^a (ⁱ )

∑

₌ ⁼

= ^j

k l

m

n

l

m

o

m

|

mediaPr ( ) ( )Pr{ ( )}

Concetti e formule un po’

complicati: e poi come si stabilisce quale sia una distribuzione realistica?

Il caso medio

Se ^a (ⁱ ) ha cardinalità finita ^p e Pr è uniforme:

) ( ogni per 1 }

Pr{ ^s ^r ^q

t

s

r ∈==

∑

₌ ⁼ ₌

= ^u

v

u

v w

x

y

w

x

z

x

|

media( ) ( )1 1 ( )

allora il valore atteso diventa una “ semplice” media:

(7)

Tempo degli algoritmi ricorsivi

costo volte

{|}~|

(, , ) ₁ 1

Pre: vettore di dimensione > ≥ Post: ritorna il minimo in [..]

| = ^} 2 1

} [] 3 1

/

p ←^{A|^}~^| (, +1, ) ₄+ ^g(^h −1) 1

| [] < ^p ^} 5 1

} [] 6 1

/

} p

7 1

h = − + 1

Tempo degli algoritmi ricorsivi

Considerando il caso peggiore quando ^h > 1:

+

−

=

+ + + + +

−

= ) 1 (

} , max{

) 1 ( )

( ₁ ₂ ₄ ₅ ₆ ₇

Quindi una definizione implicita di ^g (^h) è





>

+

−

= =

1 se ) 1 (

1 ) se

(

dove = ₁+ ₂+ ₃.

Tempo degli algoritmi ricorsivi

Per ottenere una forma esplicita svolgiamo:

) ( ) 1 ( ) 1 (

0 per ) (

2 ) 2 ( )

2 (

) 1 ( ) (

− +

=

− +

=

<

≤ +

−

=

+

−

= + +

−

= +

−

=

che ha la stessa forma della funzione tempo di ^{|^}|.

(8)

Tempo degli algoritmi ricorsivi

Quante sono le mosse necessarie per spostare con l’ algoritmo

¡.¢} |

una torre di ^h dischi?

£¥¤¦¨§©

(^ª^«¬^®^¯°^®, ^±®^ª^°^²^¯³´^²^«/¯®, ^³µª^²^¶^²^«: Torre)

©·

la torre che si trova sopra ^ª^«¬^®^¯°^® è vuota ^¸^¹º^¦ sposta il disco in ^ª^«¬^®^¯°^® su ^±®^ª^°^²^¯³/´^²^«¯® ^» (1) = 1

º½¼¾º

Hanoi (Sopra(^ª^«¬^¨®^¯°^®), ^³µ/ª^²^¶^²^«, ^±®^ª^°^²^¯³/´^²^«/¯®) ^» (^¯ − 1) sposta il disco in ^ª^«¬^®^¯°^® su ^±®^ª^°^²^¯³/´^²^«¯® 1 Hanoi (^³µ/ª^²^¶^²^«, Sopra(^±®^ª^°^²^¯³´^²^«¯®), ^ª^«¬^¨®^¯°^®) ^» (^¯ − 1)

Tempo degli algoritmi ricorsivi





>

+

−

= =

1 se 1 ) 1 ( 2

1 se ) 1

( ^À ^¿ ^¿

¿

ÀSvolgendo

Á

Â

Á

Ã Á

Ã

Á

ÃÁ

Ã

Á

Ã ÄÅ Å

Ä <≤+−

=

+ +

−

= + +

−

= +

−

=

∑

₌⁻²^per⁰

) ( 2

1 2 ) 2 ( 4 1 ) 1 ) 2 ( 2 ( 2

1 ) 1 ( 2 ) (

1 0

Æ

si ottiene

Quando ^Ç = ^È – 1, usando la formula per la serie geometrica

1

1 1

0 −

= ⁺−

∑^Ì=^Ê ^ÉËÊ^Ì ^É^É ^otteniamo ⁽⁾⁼²⁻¹⁺

∑

⁻₌₀²²⁼

∑

^ÍÎ₌⁻¹₀²Î⁼²₂^Í₋⁻₁¹⁼²^Í⁻¹

ÍÎ Î

Í

Ï

Ð

Il metodo di “ iterazione”

Per risolvere:





>

+ +

= Ò Ó Ò ≤^Ñ

ÔÕ

Ò

Ö

×Ø

Ñ

Ò

Ù

Ò

Ø

se ) ( )) ( (

) se

(

(con ^Ú (^È ) < ^È ) si itera la definizione su ^È > ^Û:

Ü=

+ + + +

=

+ +

= ^Ý

Þ

ß/à

Ý

Þ

á

ß/à

Þ

á

âã

â Ý

Þ

ß/à

Þ

á

âã

Þ

ã

) ( ) )) ( ( ))) ( ( ( (

) ( )) ( ( ) (

cercando di individuare una forma

) , ( ) , , ( )) ( ( ) ,

(^ì ^ä ^ë ^ê ^[^] ^ç ^é ^è ^ç ^ä ^æ ^å ^ä

í î

+ +

⋅

Se se ^È > ^Û e ^Ç è il min. t.c. ^Ú ^[^ï^](^È ) ≤^Û, allora, ) , ( ) , , ( ) , ( )

(^ó ^ø ^÷ ^ð ^ö ^õ ^ô ^ó ^ð ^ò ^ñ ^ð

ù ++⋅=

Ú

[^ï](^È ) = ^Ú (… ^Ú (^È )…) ^Ç volte

(9)

Come confrontare funzioni

• Sappiamo che il tempo di calcolo non è un numero ma una funzione

• Per confrontare il tempo di calcolo di due algoritmi dobbiamo confrontare tra loro funzioni

Come è possibile confrontare tra loro oggetti

infiniti?

Come confrontare funzioni

100 200 300 400 500 600 700 1000

2000 3000 4000 5000 6000 7000

Ú (^ú ) = 7^ú

û (^ú) = ^ú²/ 75

Ú (^ú ) < ^û (^ú) quando ^ú > 525

Trascuriamo un numero finito di casi

20 40 60 80 100

5000 10000 15000 20000

Sempre che quelli non siano

proprio i più frequenti!

Possiamo allora trascurare un numero

finito di casi

(10)

Le costanti non contano (veramente?)

ü dimensione massima di un problema trattabile col computer

ý

1usando un algoritmo che impiega tempo ^þ (^È ) = 2^ÿ:

+

≈

+

=

′

⇔

⋅

=

⇔

= ^′

′

10

1000 log

2 1000 2 1000 2

2

Costruiamo un computer 2

1000 volte più veloce

Quanto vale ′ se

? 1000 2 2^′ =

Le costanti non contano (veramente?)

20 40 60 80 100

5000 10000 15000 20000

(

ÿ

) = 100

ÿ

(

ÿ

) = 2

ÿ

2

•L’ algoritmo A è migliore dell’ algoritmo B per > 50;

• Rimpiazzare B con A è meglio che raddoppiare la velocità del computer:

0 ) 2 1000 (

) 1000 ( ) 2 100 (

) 100

( = =

Le costanti non contano perché

•

Quando la complessità è più che polinomiale, moltiplicando per una costante la dimensione massima di un problema trattabile praticamente non cambia

•

Anche se la complessità è polinomiale, la

“ velocità” di crescita di una funzione non dipende dalla scelta della costante

•

La stima esatta delle costanti è impossibile in

pratica (diversità delle architetture, efficienza dei

compilatori, astrazione circa il tempo impiegato da

istruzioni di diverso tipo) e conviene astrarne in

teoria

(11)

Ordini di grandezza: 2-grande

0

( )

) ( ) ( . ,

0 )) ( ( )

( ₀ ₀

≤>∀>∃⇔∈

P. Bachmann 1892

Confronto asintotico tra funzioni

¬ ≤ ⇔ ∃^∞. ¬() ≤() dove ∃^∞. P() ⇔ ∀ ∃ ≥. P().

Oss. ∀^∞. P() ⇔ ¬ ∃^∞. ¬ P()

∃^∞. P() ⇔ ¬ ∀^∞. ¬ P()

≤ ⇔ ∀^∞. () ≤()

dove ∀^∞. P() ⇔ ∃ ∀ ≥. P().

La relazione ≤ è un preordine

≤ non è tricotomica, essendovi funzioni inconfrontabili:

() = 1 se pari

0 se dispari () = 0 se pari 1 se dispari

≤ non è un ordine parziale, non essendo antisimmetrica:

≤ ∧ ≥ ⇔ ∃ ∀ ≥. () = ()

In generale ≠ 0.

La relazione ≤ è soltanto un preordine (riflessiva e transitiva). Infatti:

(12)

Le costanti non contano

Per ogni , , e per ogni costante > 0

( ) ∈ ( ⋅ ( )) ⇔ ( ) ∈ ( ( ))

Per ogni

,

, e per ogni costante

> 0

(

) ∈

(

⋅

(

)) ⇔

(

) ∈

(

))

⇒) se q.o. ( ) ≤ ⋅ ⋅ ( ) allora ⋅ è la costante cercata.

⇐) esistono > 0 e 0tali che ( ) ≤ ⋅ (), per ogni ≥ ₀

posto ^! = / (esiste perché ≠ 0), abbiamo ^! > 0 e

( ) ≤ ⋅ () = ^! ⋅ ⋅ ( )

per ogni ≥ 0^" ^# (1) include l’ insieme delle funzioni costanti

Ordini di grandezza: 2-grande

3 Q

²

+ 7 Q + 8 ∈ 2(Q

²

)

) ( ) ( .

, Q

₀

Q Q

₀

I Q FJ Q

F ∀ ≥ ≤

∃

$&%

(^')

((⁾) ∈^* (^%(⁾))

( (^')

? 3 Q

²

+ 7 Q + 8 ≤ c· Q

²

Ordini di grandezza: 2-grande

3 Q

²

+ 7 Q + 8 ∈ 2(Q

²

)

) ( ) ( .

, Q

₀

Q Q

₀

I Q FJ Q

F ∀ ≥ ≤

∃

$&%

(^')

((⁾) ∈^* (^%(⁾))

( (^')

4 ? 3 Q

²

+ 7 Q + 8 ≤ 4· Q

²

(13)

Ordini di grandezza: 2-grande

3 Q

²

+ 7 Q + 8 ∈ 2(Q

²

)

) ( ) ( .

, Q

₀

Q Q

₀

I Q FJ Q

F ∀ ≥ ≤

∃

$&%

(^')

((⁾) ∈^* (^%(⁾))

( (^')

4 3·1

²

+ 7·1 + 8 ≤ 4·1

²

1

Ordini di grandezza: 2-grande

3 Q

²

+ 7 Q + 8 ∈ 2(Q

²

)

) ( ) ( .

, Q

₀

Q Q

₀

I Q FJ Q

F ∀ ≥ ≤

∃

$&%

(^')

((⁾) ∈^* (^%(⁾))

( (^')

4 3·9

²

+ 7·9 + 8 ≤ 4·9

²

9 314 324

Ordini di grandezza: 2-grande

3 Q

²

+ 7 Q + 8 ∈ 2(Q

²

)

) ( ) ( .

, Q

₀

Q Q

₀

I Q FJ Q

F ∀ ≥ ≤

∃

$&%

(^')

((⁾) ∈^* (^%(⁾))

( (^')

4 3·8

²

+ 7·8 + 8 ≤ 4·8

²

8 3·8

²

+ (7+1)·8

(14)

Ordini di grandezza: 2-grande

2

7 8 4

3 8 Q Q Q

Q ≥ ⇒ + + ≤

2 2

2

3 4 8

7

⁺ + ≤ ⁺ − ⁺ =⁺ La tesi equivale a

Dividendo per ^,: ^-

-

≤ + 8

7

Ma 1

8 8

8⇒8≤ =

≥ ^.

. e quindi ^/

/

≤

= +

≤ +8 7 1 8 7

Ordini di grandezza: 2-grande

Se S(Q) è un polinomio di grado N allora S(Q) ∈ 2(Q

⁰

)

Se S(Q) è un polinomio di grado N allora S(Q) ∈ 2(Q

⁰

)

1

2 2

1

2 2

1

2 2

2 3

4

5

3

5

5 3

3

5

3

6 )1()(

0 0

0

+

≤

⋅

=

≤

=

∑

₌

∑

₌

∑

₌

dove ⁷ = max{⁷⁹⁸: 0 ≤^: ≤^;}.

I termini di grado inferiore si possono ignorare

Ordini di grandezza: 2-grande

Se S(Q) è un polinomio di grado K > N e coeff. dir. positivo, allora S(Q) ∉ 2(Q

⁰

) Se S(Q) è un polinomio di grado K > N e coeff. dir. positivo, allora S(Q) ∉ 2(Q

⁰

)

Tutto ciò che conta in un polinomio è il grado

P.a. se ^< (⁼) ∈^> (^=@?), allora se ⁷ è il coeff. direttore di ^< , q.o.

0 qualche per )

( ≤ >

≤^D ^B ^ACB ^A

E B FF G

H

I

J

H

I

J

I@J

HKJ L

M

L

M

L

M =≤⇔≤⇔≤ ⁻⁻ //

ma

da cui una contraddizione quando ^, > ^N .

(15)

Ordini di grandezza: 2-grande

Riassumendo:

se

^O

<

^P

allora

^Q

(

^RTS

) ⊆

^Q

(

^RTU

) ma

^Q

(

^RTU

) ⊄

^Q

(

^RTS

)

Inclusioni

> (1) ⊆^> (log ^, )

> (1) ⊆^> (log ^, ) log ^, è sup. illimitata, mentre

V (^,) ∈^> (1) ⇒ ∃^W ∀^∞^,9X^V (^, ) ≤^W

> (log ^, ) ⊆^> (^, )

log ^, ≤^, ⇔^, = 2^log^Y ≤ 2^Y perché^, < 2^Y per ogni ^, ,

> (^, ) ⊆^> (^, log ^,)

, > 2 ⇒ log ^, > 1 ⇒^, log ^,[Z\,

Inclusioni 2(Q

^]

) ⊂ 2(2

^{^}

) 2(Q

^]

) ⊂ 2(2

^{^}

)

) ( ), ( ) 0

( )

lim ( ^_ ^` ^a ^a ^` ^_

b

a b

_

c ∉∈⇒=∞→

per ogni^W > 0, 0 ≤^V (^, )/^d (^, ) < ^W q.o., quindi^V (^, ) < ^Wd (^, ) q.o.,

(16)

Inclusioni 2(Q

^]

) ⊂ 2(2

^{^}

) 2(Q

^]

) ⊂ 2(2

^{^}

)

) ( ), ( ) 0

( )

lim ( ^_ ^` ^a ^a ^` ^_

b

a b

_

c ∉∈⇒=∞→

contraddizione

q.o.

) (

) ( q.o. 1

) ( ) ( . 0 )

( f ^ee

g

h

e

hg

e

f

h

g

i

f ≤⇒≤>∃⇒∈

P.a.

Inclusioni 2(Q

^]

) ⊂ 2(2

^{^}

) 2(Q

^]

) ⊂ 2(2

^{^}

)

) ( ), ( ) 0

( )

lim a (bb ^_ ^` ^a ^a ^` ^_

_

c ∉∈⇒=∞→

2 0 lim_→_∞ jk =

j l

Le funzioni esponenziali crescono più velocemente delle polinomiali

Classificazione delle funzioni

C os tan te Lo ga ritm ica Po li lo ga ritm ica Po lin om ial e E sp on en tzi ale Po li. E sp D op p. E sp

(log n)⁵ n⁵ 2⁵ⁿ 5 log n

5 2ⁿ⁵ 2²⁵ⁿ

⊆

⊆ ⊆ ⊆ ⊆ ⊆

(17)

n log n n n n log n n² n²

2 1 1,41 2 2 4 8

4 2 2 4 8 16 64

8 3 2,83 8 24 64 512

16 4 4 16 64 256 4.096

32 5 5,66 32 160 1.024 32.768

64 6 8 64 384 4.096 262.144

128 7 11,31 128 896 16.384 2.097.152 256 8 16 256 2.048 65.536 16.777.216 512 9 22,63 512 4.608 262.144 134.217.728 1.024 10 32 1.024 10.240 1.048.576 1.073.741.824

2ⁿ

4 16 256 65.536 4.294.967.296

1,84 x 10¹⁹ 3,40 x 10³⁸ 1,15 x 10⁷⁷ 1,34 x 10¹⁵⁴ 1,79 x 10³⁰⁸ n³

Funzioni ordinate per velocità di crescita

Algebra di 2-grande

Spesso leggiamo eguaglianze del tipo ) 4 (

1 ), 2 (

1^m 2+^m =ⁿ ^m 2 ^m 2=ⁿ ^m 2

Prese alla lettera conducono ad assurdità: ² ² 4 1 2 1ô +ô = ô

p(^q) = ^r (^s (^q )) si interpreta come un’ equazione “ a senso unico” , con cui rimpiazziamo una funzione con il suo

ordine di grandezza

Algebra di 2-grande

Definiamo:

p (^q ) + ^r (^s (^q)) = {^t : ∃^s ′∈^r (^s (^q )) . ∀^∞^q . ^t (^q ) ≤^p (^q ) + ^s ′(^q )}

p (^q ) ⋅^r (^s (^q )) = {^t : ∃^s ′∈^r (^s (^q )) . ∀^∞^q . ^t (^q ) ≤^p (^q ) ⋅^s ′(^q )}

Allora ne segue:

p (^q ) + ^r (^s (^q )) = ^r (^p (^q) + ^s (^q ))

p (^q ) ⋅^r (^s (^q)) = ^r (^p (^q ) ⋅^s (^q )).

Similmente definiamo

r (^p (^q )) + ^r (^s (^q )) =

{^t : ∃^p ′∈^r (^p (^q )) ∃^s ′∈^r (^s (^q ))

∀^∞^q . ^t(^q ) ≤^p ′(^q ) + ^s ′(^q )}, ed ^r (^p (^q )) ⋅^r (^s (^q )) analogamente.

(18)

Algebra di 2-grande

Ne deriva:

p (^q ) = ^r (^p (^q))

u ⋅^r (^p (^q)) = ^r (^p (^q )) ^u costante

r (^p (^q )) + ^r (^s (^q )) = ^r (^p (^q) + ^s (^q ))

r (^p (^q )) + ^r (^p (^q)) = ^r (^p (^q ))

p ≤^s ⇒^r (^p (^q )) + ^r (^s (^q )) = ^r (^s (^q ))

r (^p (^q )) ⋅^r (^s (^q)) = ^r (^p (^q ) ⋅^s (^q )) Perciò ad esempio:

r (1) + ^r (1) = ^r (2) = ^r (1) ma

q ⋅^r (1) = ^r (^q ) (^q è una variabile!)

Una semplice applicazione

v[wxyz{|~}C|xzx

(Matrice A, int ) // Post. costruisce la matrice identità di ordine

y~

:= 1 ^x

y

j := 1 ^x A[,] := 0;

y~:= 1 ^x

A[,] := 1;

T₁() ≤₁= (1) T₂() = ⋅ T₁() = ⋅ (1) = () T₃() = ⋅ T₂() = ⋅ () = (²) T₄() ≤₂= (1)

T₅() = ⋅ T₄() = ⋅ (1) = ()

T() = T₃() + T₅() = (²) + () = (²+ ) = (²)

K

~

K

T

~

Il metodo di sostituzione

• Si indovina la soluzione

• Si verifica induttivamente che la soluzione sia tale.

T(^q ) = 2T(^q /2) + ^q Soluzione: T(^q ) ≤^u ^q log ^q

T(^q) ≤ 2 (^u (^q /2) log (^q/2)) + ^q ip. ind.

= ^u ^q log (^q/2) + ^q

= ^u ^q log ^q –^u ^q log 2 + ^q

u q log ^q –^u ^q + ^q

≤ ^u ^q log ^q (se ^u ≥ 1)

(19)

Il metodo di sostituzione

Quanto vale ^u ?

Se T(1) = 1, allora T(1) ≤^u 1 log 1 = 0 non può valere!

Ma T(2) ≤û 2 log 2, T(3) ≤û 3 log 3, valgono per û ≥ 2.

Tanto basta: il confine superiore cercato è asintotico.

Attenzione: indovinando T(^q ) = ≤^u ^q si può “ dimostrare” la tesi T(^q ) = ^r (^q):

T(^q ) ≤ 2(^u ^q /2) + ^q ip. ind.

= ^u ^q + ^q

= ^r (^q ) Errore!!!

dovevamo provare (^q ) < ^u^q per una data ^u

2-grande ed R-piccolo

Se ^p (^q) = ^r (^s (^q )) e ^s ≤^t , allora ^p (^q ) = ^r (^t (^q )): quanto “ buono”

è questo confine superiore?

p

(^q ) = (^s (^q )) sse ∀^u > 0 ∀^∞^q. 0 ≤^p (^q ) < ^u ^s (^q).

Se ^p (^q) = (^s (^q)) allora ^p è un infinitesimo di ^s , quindi ^s non è un confine superiore “ stretto” di ^p.

Osserviamo infatti che, se ^s è positiva non nulla:

) 0 (

) )) (

( ( )

( ⁼ ^⇒

lim

_→_∞ ⁼

Ω e Θ

Supposto che ^s sia asintoticamente non negativa:

p (^q ) = Ω(^s (^q )) sse∃^u ∈ R⁺\{0} ∃^q 0∈ N ∀^q ≥^q 0.

u ⋅^s (^q ) ≤^p (^q ).

p (^q ) = Θ(^s (^q)) sse∃^u1

u

2∈ R⁺\{0} ∃^q 0∈ N ∀^q ≥^q0.

u

1⋅^s (^q ) ≤^p (^q ) ≤^u₂⋅^s (^q ).

¡¢£¥¤

p (^q ) = Θ(^s (^q )) ⇔^p (^q) = ^r (^s (^q )) ∧^p (^q ) = Ω(^s (^q)).

(20)

Notazione asintotica

¬

&®

¬(^¯) = ^° (^®(^¯))

&®

¬ ¬

(^¯) = Ω(^®(^¯))

1

®

2

®

¬

¬(^¯) = Θ(^®(^¯))