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)\)

Note

This workspace is provided for your convenience. You can use this activecode window to try out anything you like.




(prova)

Next Section - La Ricerca Sequenziale