Esercizi lezione 4 - Costo Algoritmi (0 to 9)

[notedo]

[notedo]

Es. 0: analizzando il ciclo for la complessità è Θ(n), ma il professore considera un n molto grande e quindi viene eseguito subito l'if, la complessità risulta quindi Θ(1)

Es.1: se n è dispari entriamo nell'if e la complessità risulta Θ(1), invece se n è pari facciamo n-2 a ogni iterazione fino a quando n diventa 0, quindi generalizzando cosa succede durante le iterazioni abbiamo n-2i = 0 e con un po' di passaggi algebrici otteniamo $i=n/2$ che è uguale a $1/2n$, quindi possiamo togliere la costante moltiplicativa e la complessità risulta Θ(n)

Es.2: Guardando l'immagine è facile convincersi di cosa succede ad ogni iterazione, generalizzando, abbiamo x=i-1. Sappiamo che il ciclo si fermerà quando $x^{2} < n$ quindi eseguiamo i passaggi nella parte destra dell'immagine e otteniamo che la complessità è Θ(√n)

Es.3: La prima osservazione è che quello che succede ad r non ci interessa, generalizzando poi cosa succede ad n nelle varie iterazioni otteniamo $n/3^i$, il ciclo while si ferma quando n>1 quindi eseguiamo i passaggi nella parte a destra dell'immagine e otteniamo Θ(log(n))

Es.4: La prima cosa da osservare in questo esercizio è che il primo for ci da il valore di t che ci servirà nel secondo ciclo for, quindi, generalizziamo cosa succede a t nelle iterazioni del primo for, osserviamo che 3^i non è altro che 3^n perché il ciclo for viene eseguito n volte. Successivamente generalizziamo cosa succede a x e a t nel ciclo while, utilizzo una lettera diversa per indicare l'iterazione essendo due cicli distinti. A questo punto è facile convincersi che la complessità sia Θ(3^n), il fratto 4 lo tolgo perché è una costante moltiplicativa

Es. 5 Il ragionamento di questo esercizio è pressoché identico agli esercizi descritti sopra, nell'immagine si può vedere sia la generalizzazione delle iterazioni, sia i passaggi algebrici

Es.6 Ci sono due modi per approcciare questo esercizio, il primo si basa sul capire quante volte vengono eseguiti i vari cicli, il secondo sul capire il funzionamento complessivo del programma

Primo modo (più meccanico): Il while viene eseguito n volte, il for viene eseguito t+1+1+1... volte ogni volta perché t viene incrementato di 1 a ogni while, notiamo che quando u arriva a n anche t arriva ad n quindi anche il for viene eseguito n volte

Secondo modo(più ragionato) DA AGGIUNGERE (quello con la sommatoria):

Es.7 Dagli esercizi precedenti, risulta facile accorgersi che quando una quantità viene divisa per un numero, la complessità risulta essere log(n) che è la complessità del primo ciclo while, inoltre a noi serve sapere il valore di p che andremo ad usare nel secondo while. Essendo che il primo ciclo viene eseguito log(n) volte, l'operazione +1 viene eseguita log(n) volte, quindi abbiamo p = log(n). Per il secondo while dobbiamo togliere a ogni iterazione p da n, quindi n = p*i cioé togliamo p tante volte quante sono le iterazioni, con i soliti passaggi algebrici otteniamo che i = n/log(n). Ora abbiamo Θ(log(n)) e Θ(n/log(n)) e prendendo il più veloce otteniamo che la complessità è Θ(n/log(n))

Es.8 Come nell'esercizio precedente, la complessità del primo while è log(n), ora a noi serve il valore p, noi facciamo l'operazione +2 log(n) volte quindi p =2log(n), l'istruzione dopo dice che p=p*p quindi il nostro nuovo p è 4log^2(n). All'interno del secondo while abbiamo un for che viene eseguito p volte quindi 4*log^2(n) volte, che però dipende dal numero di volte in cui eseguiamo il ciclo while esterno. Sapendo che i viene incrementata di 1 ogni volta e facendo i soliti passaggi algebrici (i^3=n) abbiamo $i = \sqrt[3]{n}$, moltiplicando le due complessità abbiamo $\sqrt[3]{n} \times \log^2(n)$ che è più veloce della complessità del primo while, quindi la nostra complessità risulta Θ( $\sqrt[3]{n} \times \log^2(n)$ )

Es.9 La prima cosa che dobbiamo osservare in questo esercizio è che il valore di j è già stabilito, quindi la complessità del primo ciclo while è costante Θ(1). L'unica cosa che dobbiamo guardare quindi è il while all'interno del while e con il metodo adottato negli esercizi precedenti è facile arrivare alla conclusione che la complessità sia Θ(log(n))