Esercizi¶
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
Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:
for i in range(n): k = 2 + 2
Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:
i = n while i > 0: k = 2 + 2 i = i // 2
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
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
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
Fornire l’analisi di complessità (O-grande) del seguente frammento di codice:
i = n while i > 0: k = 2 + 2 i = i // 2
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
Scrivere una funzione che dato un array con interi compresi tra 0 e 9, calcola le frequenze dei valori compresi tra 0 e 9
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.
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.
Scrivere una funzione che dati due insiemi di numeri interi restituisce il numero di elementi nell’intersezione. Implementare una soluzione con tempo O(n2) e spazio aggiuntivo O(1).
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).
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).
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.
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(n2), 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)