Tempo di esecuzione di una funzione

[Andrew Ryan]

Devo calcolare il tempo di esecuzione di questa funzione:

fun(int n)
i=1,a=1;
while(i <= n){
j=10;
while(j <= 1000){
a=2a;
j++;
}
i++;
}

Ho svolto l'esercizio in questo modo:

riga 2 (1° while): n volte + 1
riga 4 (2° while): 1000 volte + 1

quindi per calcolare il tempo di esecuzione mi basta moltiplicare il costo del primo while per quello del secondo,ottenendo (n +1)1001 ovvero O(n)

è corretto?

[apatriarca]

j viene inizializzato a 10, non zero, da quello che vedo. Per cui il while interno viene eseguito 991 volte. In quello esterno i parte da 1, per cui il numero di esecuzioni è n, non n+1. Ma a parte questi errori, la complessità è giusta.

[Andrew Ryan]

"apatriarca":j viene inizializzato a 10, non zero, da quello che vedo. Per cui il while interno viene eseguito 991 volte. In quello esterno i parte da 1, per cui il numero di esecuzioni è n, non n+1. Ma a parte questi errori, la complessità è giusta.

ho capito gli errori,gentilmente sai dove poter trovare degli esercizi completi di soluzione per quanto riguarda questo argomento? ho provato a vedere nel topic in evidenza delle dispense online ma molti link non funzionano più

[apatriarca]

Non ti saprei dire.. ma non è difficile venir fuori con un enorme quantità di problemi di questo tipo. Per esempio, calcola la complessità di:

int i = 10;
while (i*i < n) {
    i *= i;
    i -= 3;
}

[Andrew Ryan]

"apatriarca":Non ti saprei dire.. ma non è difficile venir fuori con un enorme quantità di problemi di questo tipo. Per esempio, calcola la complessità di:

int i = 10;
while (i*i < n) {
i *= i;
i -= 3;
}

Mi trovo in difficoltà,come calcolo la ricorrenza in questo caso? provo a buttarla li,nella prima iterazione mi trovo con i elevato alla potenza di 4,alla seconda iterazione elevato alla potenza di 8,e così via,però dipende anche da quanto è grande n,provo a dire $ O(10^(4*log_10(n))) $ però sinceramente non so se è giusto e non saprei arrivarci facendo un calcolo

Ho comunque provato a fare altri esercizi,forse anche più difficili di questo,e mi sono riusciti

[apatriarca]

Ti faccio prima di tutto notare che \(i\) viene modificata solo all'interno del ciclo e non nella condizione del while... La variabile \(i\) viene aggiornata quindi in base alla regola \( i_{t+1} \gets i_t^2 - 3 \) (\( i_0 = 10 \)) e termina quando \( i_t^2 \geq n \).

Per darti una idea di cosa stiamo parlando. Questi sono i valori di \(i\) per le prime \(5\) iterazioni:
\[ 10, 97, 9406, 88472833, 7827442179045886 \]

[apatriarca]

Probabilmente ho esagerato. Non ho pensato molto a quale fosse esattamente la complessità e così com'è è tutt'altro che facile. Lo modifico in modo da rendertelo più semplice.

int i = 2;
do {
    i *= i;
} while (i < n);

La soluzione che hai fornito è molto distante da quella esatta. Devi calcolare il numero di iterazioni e non stimare come cresce l'indice. Ti faccio comunque osservare, che se un numero \(k\) viene elevato alla quarta ad ogni iterazione, il suo valore dopo \(s\) iterazioni sarà \( k^{4^s} \)

[Andrew Ryan]

"apatriarca":Probabilmente ho esagerato. Non ho pensato molto a quale fosse esattamente la complessità e così com'è è tutt'altro che facile. Lo modifico in modo da rendertelo più semplice.

int i = 2;
do {
    i *= i;
} while (i < n);

La soluzione che hai fornito è molto distante da quella esatta. Devi calcolare il numero di iterazioni e non stimare come cresce l'indice. Ti faccio comunque osservare, che se un numero \(k\) viene elevato alla quarta ad ogni iterazione, il suo valore dopo \(s\) iterazioni sarà \( k^{4^s} \)

Riguardo quest'ultimo algoritmo,noto che "$ i $ cresce come $ 2^(2^t) $ dove si assume che $ t $ sia l'iterazione,può essere che la complessità sia $ O(log_2(n)) $ ?

[hamming_burst]

"Andrew Ryan": ho provato a vedere nel topic in evidenza delle dispense online ma molti link non funzionano più

i link con questo tipo di esercizi a me funzionano, almeno se è al post che ho pubblicato io a cui ti riferisci:
esercizi: http://www.dipmat.unipg.it/%7Epinotti/C ... 0.wsol.pdf
soluzioni: http://www.dipmat.unipg.it/%7Epinotti/C ... ciziC0.pdf

"apatriarca":Ti faccio prima di tutto notare che \(i\) viene modificata solo all'interno del ciclo e non nella condizione del while... La variabile \(i\) viene aggiornata quindi in base alla regola \( i_{t+1} \gets i_t^2 - 3 \) (\( i_0 = 10 \)) e termina quando \( i_t^2 \geq n \).

Per darti una idea di cosa stiamo parlando. Questi sono i valori di \(i\) per le prime \(5\) iterazioni:
\[ 10, 97, 9406, 88472833, 7827442179045886 \]

ti sei impegnato è
metto il spoiler la possibile soluzione.

se non ho sbagliato, dobbiamo vedere quando $i_t^2 = n\ $ (quando maggiore importa poco).
ad ogni iterazione $i$ aumenta di $i^2-3$.
La condizione del ciclo viene confrontata con $(i^2-3)^2 < n$
perciò le iterazioni si iterrompono quando $(i^2-3)^2 = n$

con qualche calcolo, dato in pasto a wolfram, tale equazione ha quattro soluzioni, ma impostando la condizione iniziale che $i=10$
l'unica soluzione ammessa in $n$ è $i = \sqrt(3 + sqrt(n))$

perciò la complessità di questo codice è $O(root(4)(n))$

[apatriarca]

@Andrew Ryan: non credo che cercare di indovinare una tra le complessità che hai già visto sia un buon modo di risolvere questo tipo di problemi. Qui hai che le interazioni si interrompono quando \( 2^{2^t} = n \) e quindi quando \( t = \log_2 (\log_2 n). \) La complessità è quindi \(O\bigr(\log_2 (\log_2 n)\bigr)\).

@hamming_burst: il calcolo della complessità del codice precedente è più complicato di così.. Se \(f(x) = x^2 - 3\) devi trovare il valore \(t\) per cui \( \bigl(f^t(10)\bigr)^2 \geq n \). Usando la definizione di \(f\), la relazione quindi diventa \( f^{t+1}(10) + 3 \geq n. \) Vogliamo quindi trovare il valore di \(t\) per cui \( f^{t+1}(10) = n - 3. \) Il problema a questo punto può essere a mio parere risolto in due modi. Il primo potrebbe essere quello di determinare una formula per \( f^k \) e cercare di invertirla. Un'altra potrebbe essere quella di confrontare tale funzione con altre più semplici. Credo che la complessità sia qualcosa del tipo \( \log \log n \).

[Andrew Ryan]

"apatriarca":@Andrew Ryan: non credo che cercare di indovinare una tra le complessità che hai già visto sia un buon modo di risolvere questo tipo di problemi. Qui hai che le interazioni si interrompono quando \( 2^{2^t} = n \) e quindi quando \( t = \log_2 (\log_2 n). \) La complessità è quindi \(O\bigr(\log_2 (\log_2 n)\bigr)\).

@hamming_burst: il calcolo della complessità del codice precedente è più complicato di così.. Se \(f(x) = x^2 - 3\) devi trovare il valore \(t\) per cui \( \bigl(f^t(10)\bigr)^2 \geq n \). Usando la definizione di \(f\), la relazione quindi diventa \( f^{t+1}(10) + 3 \geq n. \) Vogliamo quindi trovare il valore di \(t\) per cui \( f^{t+1}(10) = n - 3. \) Il problema a questo punto può essere a mio parere risolto in due modi. Il primo potrebbe essere quello di determinare una formula per \( f^k \) e cercare di invertirla. Un'altra potrebbe essere quella di confrontare tale funzione con altre più semplici. Credo che la complessità sia qualcosa del tipo \( \log \log n \).

giuro che ero arrivato alla tua stessa conclusione,però provando su carta con un certo n non ero convinto,pensavo ci fosse qualcosa di sbagliato visto che quando n ad esempio vale 10,le iterazioni sono 3,quindi solo $ log_2(n) $

[apatriarca]

Stai confondendo molte cose. Un algoritmo potrebbe essere di complessità costante e avere un numero di iterazioni uguali a \(10^8\) per \(n = 1\).. Se vuoi testare qualcosa devi verificarlo per \( n \to \infty. \) Per esempio, per \( n = 2^{128} \), \(i\) assumerà valori uguali a
\[ 2 \to 2^2 \to 2^4 \to 2^8 \to 2^{16} \to 2^{32} \to 2^{64} \to 2^{128} \]
Il logaritmo di \(2^{128}\) è uguale a \(128\) mentre sono sufficienti \(7\) iterazioni del ciclo sopra.. Anche nel caso di \( n = 10 \) in ogni caso erano solo \(2\) le iterazioni ed è abbastanza in linea con \( \log \log 10 \sim 1.7 \)