Problemi di implementazione
Quando si lavora con algoritmi e strutture dati, spesso si ha l’impressione che siano estremamente complicati. Tuttavia, nella maggior parte dei casi, risultano semplici e intuitivi. Per padroneggiarli basta praticare e fare esperienza diretta, così da comprendere come funzionano effettivamente gli algoritmi.
Affrontando problemi ed esercizi specifici, ci si accorge rapidamente che alcuni gruppi e categorie di problemi possono essere considerati insieme. Condividono caratteristiche comuni che permettono di applicare determinate tecniche all’intero gruppo di problemi.
Uno di questi gruppi è costituito dai problemi di implementazione. In queste tipologie di problemi, i passaggi per giungere alla soluzione sono spesso riportati direttamente all’interno del testo del problema. Quindi, le azioni che il programma deve compiere sono già descritte. Il compito dell’ingegnere del software è implementare nel modo più efficiente possibile quei passaggi per ottenere il risultato desiderato. È importante notare che, nonostante le indicazioni siano spesso già fornite, non sempre è immediato tradurle direttamente in codice.
Sfida - Find the missing number
Given all the numbers from 1 to
n except one, you are asked to find the missing number.Input
The first line of the input contains a single integer
n (2 ≤ n ≤ 100 000).The second line of the input contains
n-1 space-separated integers (1 ≤ ≤ n).Output
The program should print the missing number.
Examples
Input | Output |
4
3 4 1 | 2 |
3
2 1 | 3 |
Tutorial sulla complessità e sulla notazione Big
Anche se il problema descritto qui sopra può sembrare semplice, la soluzione ingenua potrebbe non essere abbastanza veloce da superare tutti i test.
Un approccio ingenuo potrebbe consistere nel leggere tutti gli elementi di input in una lista e poi scorrere i numeri da
1...n, controllando se ciascun numero è presente nella lista. Se non lo è, si è trovato il numero mancante:n = int(input())
a = [int(ai) for ai in input().split()]
for i in range(1, n + 1): # n operations
if i not in a: # n operations (goes through all the elements)
print(i) # We found the solution!Questo algoritmo è in realtà molto lento. Il codice scorre tutti i numeri da
1...n e verifica se un dato numero sia presente nella lista. Il controllo “se un elemento è nella lista” è un’operazione lineare, poiché il programma deve controllare tutti gli elementi di a. Così, per controllare se i è presente, servono n operazioni (circa, dato che la lista è di n-1 elementi, ma non fa una grande differenza).In definitiva, l’algoritmo esegue circa operazioni. Il ciclo esterno compie
n iterazioni, e ciascuna richiede altrettante operazioni per verificare la presenza di un elemento nella lista. In totale, si arriva quindi a circa operazioni (nel caso peggiore).💻
I nostri computer sono in grado di eseguire ~10-100 milioni di operazioni al secondo. Quindi, se il limite di tempo per un problema è di 1 secondo (tempo tipico nei problemi algoritmici), bisognerebbe rimanere entro le 100 milioni di operazioni totali.
Nel problema sopra descritto, il valore di
n può arrivare fino a 100 000, con un totale di operazioni, cioè 10 miliardi di operazioni. Su un normale computer, ciò richiederebbe circa 100 secondi, mentre il limite di tempo per il problema è 1 solo secondo. Quindi è necessario trovare una soluzione più efficiente.Notazione Big
La notazione Big O è uno strumento matematico utilizzato per descrivere il limite superiore della complessità temporale di un algoritmo in funzione della dimensione dell’input. Fornisce una stima approssimativa del numero di operazioni che un algoritmo eseguirà in relazione alla dimensione dei dati in ingresso.
Abbiamo stimato che l’algoritmo sopra proposto esegue in totale circa operazioni. Possiamo quindi affermare che la sua complessità è .
Approfondiremo questi argomenti in modo più dettagliato, fornendo ulteriore intuizione e formalità nei prossimi segmenti del corso.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB