Vai al contenuto

Esercizi · Tempo di esecuzione

Esercizi · Capitolo 12 · ogni soluzione si apre con un clic · Capitolo 12: Tempo di esecuzione · Eserciziario, volume 4 (PDF)

Negli esercizi di questo capitolo i passi si contano con le convenzioni del capitolo «Tempo di esecuzione»: ogni esecuzione di una riga numerata dello pseudocodice (comprese le righe return) è un passo, la condizione di un ciclo while il cui corpo viene eseguito \(k\) volte viene valutata \(k+1\) volte, e le righe di un ramo che non viene percorso non vengono eseguite. Dopo aver ottenuto il numero di passi \(S(n)\), il tempo di esecuzione si esprime in funzione della dimensione dell'input \(|I|\) con una delle due regole seguenti.

Regola (A): l'input è un numero naturale \(n\). Allora \(|I|=\Theta(\log_2 n)\): esistono costanti \(c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

\[ c_1\log_2 n \le |I| \le c_2\log_2 n \qquad\Longleftrightarrow\qquad 2^{\frac{1}{c_2}|I|}\le n \le 2^{\frac{1}{c_1}|I|}, \]

poiché \(x\mapsto 2^x\) è strettamente crescente e \(2^{\log_2 n}=n\). Se \(S(n)=\Theta(n)\), esistono costanti \(a_1,a_2>0\) tali che \(a_1 n \le S(n) \le a_2 n\) per ogni \(n\) sufficientemente grande, e quindi

\[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{cioè}\qquad T(|I|)=2^{\Theta(|I|)}. \]

Regola (B): l'input è un array \(a[1..n]\) i cui elementi usano un numero costante fisso di bit. Allora \(|I|=\Theta(n)\): esistono costanti \(c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

\[ c_1 n \le |I| \le c_2 n \qquad\Longleftrightarrow\qquad \frac{1}{c_2}|I| \le n \le \frac{1}{c_1}|I|. \]

Se \(S(n)=\Theta(n^k)\) per una costante \(k\ge 1\), esistono costanti \(a_1,a_2>0\) tali che \(a_1 n^k \le S(n) \le a_2 n^k\) per ogni \(n\) sufficientemente grande, e quindi

\[ \frac{a_1}{c_2^{k}}\,|I|^k \le S(n) \le \frac{a_2}{c_1^{k}}\,|I|^k, \qquad\text{cioè}\qquad T(|I|)=\Theta(|I|^k). \]

Esercizio 12.1: Tempo di esecuzione (E1)

Si consideri il seguente algoritmo, il cui input è un numero naturale \(n\).

Algoritmo: Algoritmo 1

Input: Un numero naturale \(n\)
Output: Un numero naturale \(m\)
1function Algorithm1(n)
2\(m := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5\(m \leftarrow m+2\)
6\(i \leftarrow i+1\)
7end
8return \(m\)
9end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo somma \(2\) a \(m\) esattamente \(n\) volte, partendo da \(m=0\): determina il doppio di \(n\), cioè \(2n\).

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm1, dove \(n\) è il numero naturale dato in input. Per ogni valore di \(n\) c'è un solo input, quindi questo è anche il caso peggiore. Il corpo del ciclo viene eseguito per \(i=1,2,\dots,n\), cioè \(n\) volte, e la condizione della riga 4 viene valutata \(n+1\) volte:

    riga numero di esecuzioni
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(n\)
    8 \(1\)

    Quindi il numero totale di passi è

    \[ S(n)=1+1+(n+1)+n+n+1=3n+4=\Theta(n). \]

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. L'input è il numero naturale \(n\), quindi \(|I|=\Theta(\log_2 n)\), e \(S(n)=3n+4=\Theta(n)\). Per la regola (A) dell'introduzione agli esercizi esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{quindi}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    Il tempo di esecuzione nel caso peggiore di Algorithm1, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=2^{\Theta(|I|)}\): è esponenziale in \(|I|\), anche se il numero di passi è lineare nel valore \(n\).

Esercizio 12.2: Tempo di esecuzione (E2)

Si consideri il seguente algoritmo, il cui input è un numero naturale \(n\).

Algoritmo: Algoritmo 2

Input: Un numero naturale \(n\)
Output: Un numero naturale \(m\)
1function Algorithm2(n)
2if \(n \bmod 2 = 0\) then
3\(m := 0\)
4\(i := 1\)
5while \(i \leq n\) do
6\(m \leftarrow m+2\)
7\(i \leftarrow i+1\)
8end
9else
10\(m := n\)
11end
12return \(m\)
13end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo restituisce il doppio \(2n\) di \(n\) se \(n\) è pari. Se \(n\) è dispari, restituisce \(n\) invariato.

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm2, dove \(n\) è il numero naturale dato in input. L'esecuzione delle righe 3–7 dipende dallo specifico valore di input \(n\): prima di eseguire l'algoritmo non sappiamo se \(n\) sia pari o dispari. Definiamo una funzione

    \[ t:\N\to\{0,1\}, \]

    dove \(t(n)=1\) se \(n \bmod 2 = 0\), e \(t(n)=0\) altrimenti. In altre parole, \(t(n)\) è un oracolo che ci dice se il numero in input \(n\) è pari. Il numero di volte in cui ciascuna riga viene eseguita è:

    riga numero di esecuzioni
    2 \(1\)
    3 \(t(n)\)
    4 \(t(n)\)
    5 \(t(n)\,(n+1)\)
    6 \(t(n)\,n\)
    7 \(t(n)\,n\)
    10 \(1-t(n)\)
    12 \(1\)

    Quindi il numero totale di passi è

    \[ 1+t(n)+t(n)+t(n)(n+1)+t(n)\,n+t(n)\,n+\big(1-t(n)\big)+1=3n\,t(n)+2\,t(n)+3. \]

    Il caso peggiore si ha quando \(n\) è pari: allora \(t(n)=1\) e l'algoritmo esegue \(3n+5\) passi, mentre per \(n\) dispari ne esegue solo \(3\). Ogni dimensione dell'input di almeno due bit è la dimensione di qualche numero pari, quindi nel caso peggiore

    \[ S(n)=3n+5=\Theta(n). \]

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. L'input è il numero naturale \(n\), quindi \(|I|=\Theta(\log_2 n)\), e \(S(n)=3n+5=\Theta(n)\). Per la regola (A) dell'introduzione agli esercizi esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{quindi}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    Il tempo di esecuzione nel caso peggiore di Algorithm2, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=2^{\Theta(|I|)}\): è esponenziale in \(|I|\), anche se il numero di passi è lineare nel valore \(n\).

Esercizio 12.3: Tempo di esecuzione (E3)

Si consideri il seguente algoritmo, il cui input è un numero naturale \(n\).

Algoritmo: Algoritmo 3

Input: Un numero naturale \(n\)
Output: Un numero naturale \(s\)
1function Algorithm3(n)
2\(s := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5\(s \leftarrow s+i\)
6\(i \leftarrow i+1\)
7end
8return \(s\)
9end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo determina la somma dei primi \(n\) numeri naturali positivi:

    \[ 1+2+\cdots+n=\frac{n(n+1)}{2}. \]

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm3, dove \(n\) è il numero naturale dato in input (per ogni valore di \(n\) c'è un solo input). Il corpo del ciclo viene eseguito \(n\) volte e la sua condizione \(n+1\) volte:

    riga numero di esecuzioni
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(n\)
    8 \(1\)

    Quindi il numero totale di passi è

    \[ S(n)=1+1+(n+1)+n+n+1=3n+4=\Theta(n). \]

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. L'input è il numero naturale \(n\), quindi \(|I|=\Theta(\log_2 n)\), e \(S(n)=3n+4=\Theta(n)\). Per la regola (A) dell'introduzione agli esercizi esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{quindi}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    Il tempo di esecuzione nel caso peggiore di Algorithm3, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=2^{\Theta(|I|)}\): è esponenziale in \(|I|\), anche se il numero di passi è lineare nel valore \(n\).

Esercizio 12.4: Tempo di esecuzione (E4)

Si consideri il seguente algoritmo, il cui input è un numero naturale \(n\).

Algoritmo: Algoritmo 4

Input: Un numero naturale \(n\)
Output: Un numero naturale \(p\)
1function Algorithm4(n)
2\(p := 1\)
3\(i := 1\)
4while \(i \leq n\) do
5\(p \leftarrow p \cdot i\)
6\(i \leftarrow i+1\)
7end
8return \(p\)
9end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo determina il prodotto

    \[ 1\cdot 2\cdot \ldots \cdot n=n! \]

    (con \(0!=1\), restituito per \(n=0\)).

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm4, dove \(n\) è il numero naturale dato in input (per ogni valore di \(n\) c'è un solo input). Il corpo del ciclo viene eseguito \(n\) volte e la sua condizione \(n+1\) volte:

    riga numero di esecuzioni
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(n\)
    8 \(1\)

    Quindi il numero totale di passi è

    \[ S(n)=1+1+(n+1)+n+n+1=3n+4=\Theta(n). \]

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. L'input è il numero naturale \(n\), quindi \(|I|=\Theta(\log_2 n)\), e \(S(n)=3n+4=\Theta(n)\). Per la regola (A) dell'introduzione agli esercizi esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{quindi}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    Il tempo di esecuzione nel caso peggiore di Algorithm4, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=2^{\Theta(|I|)}\): è esponenziale in \(|I|\), anche se il numero di passi è lineare nel valore \(n\).

Esercizio 12.5: Tempo di esecuzione (E5)

Si consideri il seguente algoritmo, il cui input è un numero naturale \(n\).

Algoritmo: Algoritmo 5

Input: Un numero naturale \(n\)
Output: Un numero naturale \(c\)
1function Algorithm5(n)
2\(c := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5if \(i \bmod 2 = 0\) then
6\(c \leftarrow c+1\)
7end
8\(i \leftarrow i+1\)
9end
10return \(c\)
11end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo determina quanti numeri naturali tra \(1\) e \(n\) sono pari, cioè \(\lfloor n/2\rfloor\).

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm5, dove \(n\) è il numero naturale dato in input. La riga 6 viene eseguita solo quando \(i\) è pari, cioè \(\lfloor n/2\rfloor\) volte. Il numero di volte in cui ciascuna riga viene eseguita è:

    riga numero di esecuzioni
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(\lfloor n/2\rfloor\)
    8 \(n\)
    10 \(1\)

    Quindi il numero totale di passi è

    \[ S(n)=1+1+(n+1)+n+\lfloor n/2\rfloor+n+1=3n+\lfloor n/2\rfloor+4. \]

    Poiché \(\frac{n-1}{2}\le\lfloor n/2\rfloor\le \frac{n}{2}\), si ha \(\frac{7}{2}n+\frac{7}{2}\le S(n)\le \frac{7}{2}n+4\), quindi \(S(n)=\Theta(n)\).

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. L'input è il numero naturale \(n\), quindi \(|I|=\Theta(\log_2 n)\), e \(S(n)=3n+\lfloor n/2\rfloor+4=\Theta(n)\). Per la regola (A) dell'introduzione agli esercizi esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{quindi}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    Il tempo di esecuzione nel caso peggiore di Algorithm5, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=2^{\Theta(|I|)}\): è esponenziale in \(|I|\), anche se il numero di passi è lineare nel valore \(n\).

Esercizio 12.6: Tempo di esecuzione (E6)

Si consideri il seguente algoritmo, il cui input è un numero naturale \(n\).

Algoritmo: Algoritmo 6

Input: Un numero naturale \(n\)
Output: Un numero naturale \(q\)
1function Algorithm6(n)
2\(q := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5\(q \leftarrow q+n\)
6\(i \leftarrow i+1\)
7end
8return \(q\)
9end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo somma \(n\) a \(q\) esattamente \(n\) volte, partendo da \(q=0\): determina \(n\cdot n=n^2\).

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm6, dove \(n\) è il numero naturale dato in input (per ogni valore di \(n\) c'è un solo input). Il corpo del ciclo viene eseguito \(n\) volte e la sua condizione \(n+1\) volte:

    riga numero di esecuzioni
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(n\)
    8 \(1\)

    Quindi il numero totale di passi è

    \[ S(n)=1+1+(n+1)+n+n+1=3n+4=\Theta(n). \]

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. L'input è il numero naturale \(n\), quindi \(|I|=\Theta(\log_2 n)\), e \(S(n)=3n+4=\Theta(n)\). Per la regola (A) dell'introduzione agli esercizi esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ a_1\, 2^{\frac{1}{c_2}|I|} \le S(n) \le a_2\, 2^{\frac{1}{c_1}|I|}, \qquad\text{quindi}\qquad T(|I|)=2^{\Theta(|I|)}. \]

    Il tempo di esecuzione nel caso peggiore di Algorithm6, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=2^{\Theta(|I|)}\): è esponenziale in \(|I|\), anche se il numero di passi è lineare nel valore \(n\).

Esercizio 12.7: Tempo di esecuzione (E7)

Si consideri il seguente algoritmo, il cui input è un array \(a[1..n]\) di \(n\) numeri interi.

Algoritmo: Algoritmo 7

Input: Un array \(a[1..n]\) di \(n\) numeri interi
Output: Un numero intero \(s\)
1function Algorithm7(a, n)
2\(s := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5if \(a[i] > 0\) then
6\(s \leftarrow s+a[i]\)
7end
8\(i \leftarrow i+1\)
9end
10return \(s\)
11end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo determina la somma dei valori positivi nell'array \(a[1..n]\).

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm7 nel caso peggiore, dove \(n\) è la dimensione dell'array. L'esecuzione della riga 6 dipende dall'array in input. Definiamo una funzione

    \[ t:\{1,2,\dots,n\}\to\{0,1\}, \]

    dove \(t(i)=1\) se \(a[i]>0\), e \(t(i)=0\) altrimenti. Il numero di volte in cui ciascuna riga viene eseguita è:

    riga numero di esecuzioni
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(\sum_{i=1}^{n}t(i)\)
    8 \(n\)
    10 \(1\)

    Quindi il numero totale di passi è

    \[ 1+1+(n+1)+n+\sum_{i=1}^{n}t(i)+n+1=3n+4+\sum_{i=1}^{n}t(i). \]

    Il caso peggiore si ha quando tutti gli elementi sono positivi. Allora \(t(i)=1\) per ogni \(i \in \{1,2,\dots,n\}\), e

    \[ S(n)=3n+4+\sum_{i=1}^{n}1=4n+4=\Theta(n). \]

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. Se tutti i valori in input usano un numero costante fisso di bit, allora \(|I|=\Theta(n)\), e \(S(n)=\Theta(n)\). Per la regola (B) dell'introduzione agli esercizi (con \(k=1\)) esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ \frac{a_1}{c_2}\,|I| \le S(n) \le \frac{a_2}{c_1}\,|I|, \qquad\text{quindi}\qquad T(|I|)=\Theta(|I|). \]

    Il tempo di esecuzione nel caso peggiore di Algorithm7, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=\Theta(|I|)\): è lineare in \(|I|\).

Esercizio 12.8: Tempo di esecuzione (E8)

Si consideri il seguente algoritmo, il cui input è un array \(a[1..n]\) di \(n\) numeri interi.

Algoritmo: Algoritmo 8

Input: Un array \(a[1..n]\) di \(n\) numeri interi
Output: Un numero naturale \(c\)
1function Algorithm8(a, n)
2\(c := 0\)
3\(i := 1\)
4while \(i \leq n\) do
5if \(a[i] \bmod 2 = 0\) then
6\(c \leftarrow c+1\)
7end
8\(i \leftarrow i+1\)
9end
10return \(c\)
11end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo determina il numero di valori pari nell'array \(a[1..n]\).

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm8 nel caso peggiore, dove \(n\) è la dimensione dell'array. L'esecuzione della riga 6 dipende dall'array in input. Definiamo una funzione

    \[ t:\{1,2,\dots,n\}\to\{0,1\}, \]

    dove \(t(i)=1\) se \(a[i] \bmod 2 = 0\), e \(t(i)=0\) altrimenti. Il numero di volte in cui ciascuna riga viene eseguita è:

    riga numero di esecuzioni
    2 \(1\)
    3 \(1\)
    4 \(n+1\)
    5 \(n\)
    6 \(\sum_{i=1}^{n}t(i)\)
    8 \(n\)
    10 \(1\)

    Quindi il numero totale di passi è

    \[ 1+1+(n+1)+n+\sum_{i=1}^{n}t(i)+n+1=3n+4+\sum_{i=1}^{n}t(i). \]

    Il caso peggiore si ha quando tutti gli elementi sono pari. Allora \(t(i)=1\) per ogni \(i \in \{1,2,\dots,n\}\), e

    \[ S(n)=3n+4+\sum_{i=1}^{n}1=4n+4=\Theta(n). \]

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. Se tutti i valori in input usano un numero costante fisso di bit, allora \(|I|=\Theta(n)\), e \(S(n)=\Theta(n)\). Per la regola (B) dell'introduzione agli esercizi (con \(k=1\)) esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ \frac{a_1}{c_2}\,|I| \le S(n) \le \frac{a_2}{c_1}\,|I|, \qquad\text{quindi}\qquad T(|I|)=\Theta(|I|). \]

    Il tempo di esecuzione nel caso peggiore di Algorithm8, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=\Theta(|I|)\): è lineare in \(|I|\).

Esercizio 12.9: Tempo di esecuzione (E9)

Si consideri il seguente algoritmo, il cui input è un array \(a[1..n]\) di \(n \ge 1\) numeri interi.

Algoritmo: Algoritmo 9

Input: Un array \(a[1..n]\) di \(n \ge 1\) numeri interi
Output: Un numero intero \(m\)
1function Algorithm9(a, n)
2\(m := a[1]\)
3\(i := 2\)
4while \(i \leq n\) do
5if \(a[i] < m\) then
6\(m \leftarrow a[i]\)
7end
8\(i \leftarrow i+1\)
9end
10return \(m\)
11end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo determina il valore minimo nell'array \(a[1..n]\).

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm9 nel caso peggiore, dove \(n\) è la dimensione dell'array. Il corpo del ciclo viene eseguito per \(i=2,3,\dots,n\), cioè \(n-1\) volte. Definiamo

    \[ t:\{2,3,\dots,n\}\to\{0,1\}, \]

    dove \(t(i)=1\) se la riga 6 viene eseguita all'iterazione \(i\), e \(t(i)=0\) altrimenti. Il numero di volte in cui ciascuna riga viene eseguita è:

    riga numero di esecuzioni
    2 \(1\)
    3 \(1\)
    4 \(n\)
    5 \(n-1\)
    6 \(\sum_{i=2}^{n}t(i)\)
    8 \(n-1\)
    10 \(1\)

    Quindi il numero totale di passi è

    \[ 1+1+n+(n-1)+\sum_{i=2}^{n}t(i)+(n-1)+1=3n+1+\sum_{i=2}^{n}t(i). \]

    Il caso peggiore si ha quando

    \[ a[1]>a[2]>\cdots>a[n]. \]

    Allora \(t(i)=1\) per ogni \(i\in\{2,3,\dots,n\}\), e

    \[ S(n)=3n+1+\sum_{i=2}^{n}1=3n+1+(n-1)=4n=\Theta(n). \]

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. Se tutti i valori in input usano un numero costante fisso di bit, allora \(|I|=\Theta(n)\), e \(S(n)=\Theta(n)\). Per la regola (B) dell'introduzione agli esercizi (con \(k=1\)) esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ \frac{a_1}{c_2}\,|I| \le S(n) \le \frac{a_2}{c_1}\,|I|, \qquad\text{quindi}\qquad T(|I|)=\Theta(|I|). \]

    Il tempo di esecuzione nel caso peggiore di Algorithm9, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=\Theta(|I|)\): è lineare in \(|I|\).

Esercizio 12.10: Tempo di esecuzione (E10)

Si consideri il seguente algoritmo, il cui input è un array \(a[1..n]\) di \(n \ge 1\) numeri interi.

Algoritmo: Algoritmo 10

Input: Un array \(a[1..n]\) di \(n \ge 1\) numeri interi
Output: true or false
1function Algorithm10(a, n)
2\(i := 1\)
3while \(i < n\) do
4if \(a[i]=a[i+1]\) then
5return true
6end
7\(i \leftarrow i+1\)
8end
9return false
10end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo determina se l'array contiene due valori consecutivi uguali: restituisce true se \(a[i]=a[i+1]\) per qualche \(i\in\{1,2,\dots,n-1\}\), e false altrimenti.

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm10 nel caso peggiore, dove \(n\) è la dimensione dell'array. Se la prima coppia di valori consecutivi uguali viene trovata all'iterazione \(k\), l'algoritmo si ferma alla riga 5 dopo \(1+k+k+(k-1)+1=3k+1\le 3(n-1)+1\) passi. Il caso peggiore è quindi quello in cui non ci sono due valori consecutivi uguali: la riga 5 non viene mai eseguita e l'algoritmo controlla tutte le \(n-1\) coppie consecutive. In questo caso il numero di volte in cui ciascuna riga viene eseguita è:

    riga numero di esecuzioni
    2 \(1\)
    3 \(n\)
    4 \(n-1\)
    5 \(0\)
    7 \(n-1\)
    9 \(1\)

    Quindi il numero totale di passi è

    \[ S(n)=1+n+(n-1)+(n-1)+1=3n=\Theta(n). \]

    (e \(3n>3(n-1)+1\), quindi questo è effettivamente il caso peggiore).

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. Se tutti i valori in input usano un numero costante fisso di bit, allora \(|I|=\Theta(n)\), e \(S(n)=\Theta(n)\). Per la regola (B) dell'introduzione agli esercizi (con \(k=1\)) esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ \frac{a_1}{c_2}\,|I| \le S(n) \le \frac{a_2}{c_1}\,|I|, \qquad\text{quindi}\qquad T(|I|)=\Theta(|I|). \]

    Il tempo di esecuzione nel caso peggiore di Algorithm10, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=\Theta(|I|)\): è lineare in \(|I|\).

Esercizio 12.11: Tempo di esecuzione (E11)

Si consideri il seguente algoritmo, il cui input è un array \(a[1..n]\) di \(n \ge 1\) numeri interi.

Algoritmo: Algoritmo 11

Input: Un array \(a[1..n]\) di \(n \ge 1\) numeri interi
Output: Un numero naturale \(c\)
1function Algorithm11(a, n)
2\(c := 0\)
3\(i := 1\)
4while \(i \leq n-1\) do
5\(j := i+1\)
6while \(j \leq n\) do
7if \(a[i] < a[j]\) then
8\(c \leftarrow c+1\)
9end
10\(j \leftarrow j+1\)
11end
12\(i \leftarrow i+1\)
13end
14return \(c\)
15end

Domande

  1. Che cosa determina l'algoritmo?

  2. Determinare il tempo di esecuzione nel caso peggiore dell'algoritmo.

Soluzione

  1. L'algoritmo determina il numero di coppie di posizioni \((i,j)\), con \(1\leq i<j\leq n\), tali che

    \[ a[i]<a[j]. \]

  2. Sia \(S(n)\) il numero di passi eseguiti da Algorithm11 nel caso peggiore, dove \(n\) è la dimensione dell'array. Il ciclo esterno viene eseguito per \(i=1,2,\dots,n-1\) (la sua condizione viene valutata \(n\) volte) e, per ogni \(i\), il ciclo interno viene eseguito per \(j=i+1,\dots,n\), cioè \(n-i\) volte (la sua condizione viene valutata \(n-i+1\) volte). Quindi il corpo del ciclo interno viene eseguito una volta per ogni coppia \((i,j)\) con \(1\le i<j\le n\), e il numero di tali coppie è

    \[ P=(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}. \]

    Definiamo \(t(i,j)=1\) se la riga 8 viene eseguita per la coppia \((i,j)\), e \(t(i,j)=0\) altrimenti. Il numero di volte in cui ciascuna riga viene eseguita è:

    riga numero di esecuzioni
    2 \(1\)
    3 \(1\)
    4 \(n\)
    5 \(n-1\)
    6 \(\sum_{i=1}^{n-1}(n-i+1)=P+(n-1)\)
    7 \(P\)
    8 \(\sum_{1\le i<j\le n}t(i,j)\)
    10 \(P\)
    12 \(n-1\)
    14 \(1\)

    Quindi il numero totale di passi è

    \[ 1+1+n+(n-1)+\big(P+(n-1)\big)+P+\sum_{1\le i<j\le n}t(i,j)+P+(n-1)+1=4n+3P+\sum_{1\le i<j\le n}t(i,j). \]

    Il caso peggiore per la riga 8 si ha quando

    \[ a[1]<a[2]<\cdots<a[n]: \]

    allora \(t(i,j)=1\) per ogni coppia, e

    \[ S(n)=4n+4P=4n+2n(n-1)=2n^2+2n=\Theta(n^2). \]

    Ad esempio, per \(n=4\) e \(a[1..4]=(1,2,3,4)\) l'algoritmo restituisce \(c=6\) dopo \(S(4)=2\cdot 16+8=40\) passi.

    Esprimiamo ora il tempo di esecuzione in funzione della dimensione dell'input. Se tutti i valori in input usano un numero costante fisso di bit, allora \(|I|=\Theta(n)\), e \(S(n)=\Theta(n^2)\). Per la regola (B) dell'introduzione agli esercizi (con \(k=2\)) esistono costanti \(a_1,a_2,c_1,c_2>0\) tali che, per ogni \(n\) sufficientemente grande,

    \[ \frac{a_1}{c_2^{2}}\,|I|^2 \le S(n) \le \frac{a_2}{c_1^{2}}\,|I|^2, \qquad\text{quindi}\qquad T(|I|)=\Theta(|I|^2). \]

    Il tempo di esecuzione nel caso peggiore di Algorithm11, in funzione della dimensione dell'input \(|I|\), è \(T(|I|)=\Theta(|I|^2)\): è quadratico in \(|I|\).