Contare le operazioni con la notazione Big-O
Dalla complessità costante a quella quadratica, in parole semplici
Contare le operazioni con la notazione Big-O è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Perché contare le operazioni
Nelle gare, la velocità è fondamentale. Invece di misurare il tempo di esecuzione del codice, si stima quanti passi richiede. Questa stima rappresenta la sua complessità temporale. 🚀
Introduzione alla Big-O
La Big-O descrive come cresce il numero di operazioni al crescere della dimensione n dell'input. Ignora i dettagli minori e si concentra sull'andamento dominante.
Tempo costante O(1)
Quando il lavoro non dipende mai da n, la complessità è O(1). Leggere un elemento di una lista o eseguire un'addizione richiede sempre lo stesso tempo.
x = arr[0]
y = a + bTempo lineare O(n)
Un semplice ciclo su n elementi è O(n). Raddoppiando l'input, il lavoro raddoppia all'incirca. È il cavallo di battaglia di tutti i giorni.
for x in arr:
total += xTempo quadratico O(n al quadrato)
Un ciclo dentro un altro ciclo su n elementi è O(n^2). Per n = 1000 si tratta di un milione di passi, e da lì la crescita è rapida.
for i in range(n):
for j in range(n):
check(i, j)Tempo logaritmico O(log n)
Quando ogni passo dimezza il problema, si ottiene O(log n). La ricerca binaria raggiunge un miliardo di elementi in soli 30 passi circa. ✨
La scala di crescita
In ordine dalla più veloce alla più lenta, la comune sequenza è: O(1), O(log n), O(n), O(n log n), O(n^2). Più in alto nella lista significa che la scalabilità è migliore.
Ignorare le costanti
La Big-O ignora i fattori costanti, quindi O(2n) è semplicemente O(n). Anche due passaggi crescono linearmente, perciò il moltiplicatore non cambia la classe.
Tenere solo il termine dominante
Quando i termini si sommano, conta solo quello che cresce più rapidamente. O(n^2 + n) si semplifica in O(n^2), perché al crescere di n, n^2 domina n.
Sequenziali e annidati
Due cicli uno dopo l'altro si sommano: O(n + n) = O(n). Due cicli annidati si moltiplicano e diventano O(n^2). È la struttura dei cicli a indicare quale dei due casi si applica.
Prima il caso peggiore
Le gare valutano il caso di test più difficile, quindi si ragiona sul caso peggiore. Supponga che il ciclo venga eseguito fino in fondo, non che termini in anticipo.
Verifica rapida
È il momento di mettere alla prova il suo intuito sulla Big-O.
Riepilogo
Ora sa leggere il codice in termini di crescita: O(1), O(n), O(n^2) e O(log n). Ignori le costanti, mantenga il termine dominante e consideri il caso peggiore. 🎯
Domande Frequenti
La lezione «Contare le operazioni con la notazione Big-O» è gratuita?
Sì — il testo completo di «Contare le operazioni con la notazione Big-O» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Contare le operazioni con la notazione Big-O»?
Dalla complessità costante a quella quadratica, in parole semplici Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Contare le operazioni con la notazione Big-O»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Contare le operazioni con la notazione Big-O
- La regola pratica di 10^8
- Leggere i vincoli e scegliere la complessità
- Perché si verifica TLE e come riconoscerlo