Sommatorie Notevoli PDF

Preview

Summary

Download Sommatorie Notevoli PDF

Description

Corso di Fondamenti di Informatica Dip. Ingegneria dell’Innovazione Università del Salento

Prof. Italo Epicoco

Sommatorie Notevoli Somme di potenza

#

!𝑖 = $%&

#

! 𝑖/ = $%&

#

𝑛(𝑛 + 1) = Θ(𝑛/ ) 2

𝑛(𝑛 + 1)(2𝑛 + 1) = Θ(𝑛1 ) 6 2

𝐵6 𝑠 (𝑛 + 1)23& ! 𝑖2 = 9 : (𝑛 + 1)2;63& = Θ(𝑛 23& ) +! 𝑠−𝑘+1 𝑘 𝑠+1 6%&

$%&

Somme di esponenziali #

!𝑎$ =

$%&

#

! 𝑖 · 𝑎$ = 𝑎 #

$%&

𝑎 − 𝑎 #3& Θ(𝑎# ),???𝑎 > 1 == Θ(1),???𝑎 < 1 1−𝑎

𝑛 · 𝑎 #3& 1 − 𝑎# Θ(𝑛𝑎 # ),???𝑎 > 1 − = = Θ(1),???𝑎 < 1 (1 − 𝑎)/ 1−𝑎

𝑎(1 + 𝑎 − (𝑛 + 1)/ 𝑎# + (2𝑛/ + 2𝑛 − 1)𝑎#3& − 𝑛 / 𝑎#3/ ) Θ(𝑛/ 𝑎# ),???𝑎 > 1 == ! 𝑖 / 𝑎$ = 1 (1 − 𝑎) Θ(1 ),???𝑎 < 1 $%&

Somme di logaritmi

#

! log 𝑖 = log 𝑛! = Θ(𝑛 log 𝑛) $%&

Produttoria

#

G 𝑖 = 𝑛! = Θ(𝑛# ) $%&

Regola generale Oltre alle sommatorie e produttorie notevoli qui riportate, è possibile effettuare un’analisi asintotica delle sommatorie attraverso una maggiorazione. In tutti i casi nei quali i termini presenti nella sommatoria crescono all’aumentare del limite superiore della sommatoria, possiamo immaginare di sostituire tutti i termini della sommatoria con il termine più grande. Esempio: sia data la seguente sommatoria #

#

! √𝑖 log log 𝑖 ≤ ! I√𝑛 log log 𝑛 = 𝑛 I√𝑛 log log 𝑛

$%&

Da cui possiamo derivare

I

$%&

Corso di Fondamenti di Informatica Dip. Ingegneria dell’Innovazione Università del Salento #

Prof. Italo Epicoco

1

I

! √𝑖 log log 𝑖 = 𝑂(𝑛/ log log 𝑛)

$%&

Si fa notare che, a seguito della maggiorazione, utilizziamo la notazione O-grande e non la notazione Q-grade. Nei casi in cui invece i termini della sommatoria tendono ad un valore finito diverso da zero al crescere del limite superiore della sommatoria allora la sommatoria avrà un andamento asintoticamente lineare Esempio:

#

#

$%&

$%&

5𝑖 / ! / ≤ ! 5 = Θ(𝑛) 𝑖 +1

Nei casi in cui invece i termini della sommatoria tendono a zero al crescere del limite superiore della sommatoria allora la sommatoria tenderà asintoticamente ad un valore costante. Esempio:

#

!

$%&

𝑖/

5𝑖 = Θ(1) +1...