Big-O — dai un nome alla complessità del codice
Leggi il frammento, dai un nome alla sua complessità temporale, poi guarda la curva di crescita. Sei classi, sei turni. Gratis.
Cinque frammenti, cinque delle sei classi, ciascuna chiesta una volta.
Come si gioca
- Leggi il frammento e scegli la sua complessità temporale fra le sei.
- La curva di crescita viene disegnata dopo ogni risposta: la tua in rosso, quella giusta in verde.
- Cinque delle sei classi per partita, senza ripetizioni, quindi rispondere sempre uguale è giusto al massimo una volta.
- Le risposte giuste consecutive rendono di più. Una sbagliata azzera la serie.
Come funziona
Ogni turno mostra un breve pezzo di codice e chiede la sua complessità temporale. Rispondi, e la curva di crescita viene disegnata per te — la tua contro quella giusta — così la scelta smette di essere un'etichetta e diventa una forma che si vede. Una partita chiede cinque delle sei classi, mescolate e senza ripetizioni, quindi rispondere sempre la stessa cosa è giusto al massimo una volta — e la classe esclusa cambia, così l'ultimo turno non è mai regalato per esclusione. I frammenti sono scelti perché ognuno abbia una sola risposta difendibile: nessuna uscita anticipata, nessun costo di libreria nascosto e niente che riveli la propria complessità in un commento. L'ordinamento è preso come O(n log n) ovunque, che è ciò che offre qualunque libreria standard. Gira sul tuo dispositivo, non viene inviato nulla e non c'è niente da registrare.
La notazione O descrive come cresce il costo, non quanto vale. Un O(n²) con buone costanti batte un O(n log n) gonfio alle dimensioni che il codice reale vede di solito — ed è l'argomento di un altro gioco di questo sito.
Domande frequenti
Perché la curva è in scala logaritmica?
Perché altrimenti sei classi non stanno in un solo grafico. A n=24 una funzione a tempo costante costa 1 e una esponenziale sedici milioni: su un asse lineare cinque curve su sei sarebbero la stessa riga piatta in fondo. Una scala logaritmica trasforma ogni classe in una pendenza distinguibile, ed è quello che vale la pena vedere.
L'ordinamento è davvero O(n log n)?
Per gli ordinamenti per confronto sì: è un limite inferiore dimostrato ed è ciò che offre qualunque libreria standard. Counting sort e radix sort fanno meglio non confrontando, ma richiedono ipotesi sulle chiavi. Quando qui un frammento chiama sort(), costa n log n.
Perché non ci sono frammenti con uscita anticipata?
Perché un'uscita anticipata trasforma un caso peggiore in un caso medio, e allora la risposta non è più una sola classe. Una ricerca lineare che ritorna alla prima corrispondenza è O(n) nel caso peggiore e O(1) se la corrispondenza è sempre la prima: chiedere «la» complessità sarebbe scorretto. La ricerca binaria è l'eccezione: esce presto ed è comunque esattamente O(log n).
La serie conta?
Sì. Ogni seconda risposta giusta di fila aumenta quanto rende la successiva, fino a un tetto, quindi una partita pulita vale parecchio più di quattro giuste e due sbagliate. Una sbagliata azzera tutto.