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 e’ 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 e’ 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)