Esercizi¶

1. Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:

   for i in range(n):
      for j in range(n):
         k = 2 + 2
   

2. Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:

   for i in range(n):
        k = 2 + 2
   

3. Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:

   i = n
   while i > 0:
      k = 2 + 2
      i = i // 2
   

4. Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:

   for i in range(n):
      for j in range(n):
         for k in range(n):
            k = 2 + 2
   

5. Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:

   for i in range(n):
      for j in range(i):
            k = 2 + 2
   

6. Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:

   for i in range(n):
      for j in range(i):
         for k in range(j):
            k = 2 + 2
   

7. Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:

   i = n
   while i > 0:
      k = 2 + 2
      i = i // 2
   

8. Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:

   for i in range(n):
      k = 2 + 2
   for j in range(n):
      k = 2 + 2
   for k in range(n):
      k = 2 + 2
   

9. Scrivere una funzione che dato un array con interi compresi tra 0 e 9, calcola le frequenze dei valori compresi tra 0 e 9

10. Scrivere la funzione anagramma che dati due array di numeri interi (che sono tutti compresi tra 0 e 9, con ripetizioni) restituisce true se un array è l’anagramma dell’altro, false altrimenti in tempo lineare.

11. Scrivere la funzione anagramma che dati due array di numeri interi (che sono tutti compresi tra 0 e 1000000, con ripetizioni) restituisce true se un array è l’anagramma dell’altro, false altrimenti in tempo lineare. La memoria occupata deve essere \(O(n)\), dove n è la lunghezza dei due array in input.

12. Scrivere una funzione che dati due insiemi di numeri interi restituisce il numero di elementi nell’intersezione. Implementare una soluzione con tempo \(O(n^2)\) e spazio aggiuntivo \(O(1)\).

13. Scrivere una funzione che dati due insiemi di numeri interi restituisce il numero di elementi nell’intersezione. Sapendo che tutti i valori sono compresi tra 0 e 10, implementare una soluzione con tempo \(O(n)\) e spazio aggiuntivo \(O(1)\).

14. Scrivere una funzione che dati due insiemi di numeri interi restituisce il numero di elementi nell’intersezione. Usando i dizionari, implementare una soluzione con tempo \(O(n)\).

15. Dato un array di n interi, sostituire il valore di ciascun elemento con la somma dei valori degli elementi che lo seguono nell’array in tempo lineare.

16. Viene dato un array di dimensione N contenente (non ordinati) tutti gli interi compresi tra 1 e N + 1 ad eccezione di uno di essi e si vuole stabilire l’elemento mancante.

    Esempio: 3 4 9 2 7 1 8 6

    Manca 5

    Sono possibili almeno 4 soluzioni aventi le seguenti complessita’:

    • tempo \(O(n^2)\), spazio \(O(1)\)
    • tempo \(O(nlogn)\), spazio \(O(n)\)
    • tempo \(O(n)\), spazio \(O(n)\)
    • tempo \(O(n)\), spazio \(O(1)\)