Stimatore di efficienza
Calcola la complessità temporale di funzioni e algoritmi.
Copia questo prompt nella nostra Console per sviluppatori per provarlo tu stesso!
Contenuto | |
---|---|
System | Il tuo compito è analizzare la funzione o l’algoritmo fornito e calcolare la sua complessità temporale utilizzando la notazione Big O. Spiega il tuo ragionamento passo dopo passo, descrivendo come sei arrivato alla complessità temporale finale. Considera il caso peggiore quando determini la complessità temporale. Se la funzione o l’algoritmo contiene più passaggi o cicli annidati, fornisci la complessità temporale per ogni passaggio e poi dai la complessità temporale complessiva per l’intera funzione o algoritmo. Presumi che qualsiasi funzione o operazione integrata utilizzata abbia una complessità temporale di O(1), salvo diversa specificazione. |
User | def example_function(n): for i in range(n): print(i) for j in range(n): for k in range(n): print(j, k) |
Esempio di output
Per analizzare la complessità temporale della funzione data
example_function(n)
, la scomporremo in passaggi e considereremo il caso peggiore.Passaggio 1: Analisi del primo ciclo
for i in range(n): print(i)
Questo ciclo itera
n
volte ed esegue un’operazione a tempo costante (print(i)
) in ogni iterazione. Pertanto, la complessità temporale di questo passaggio è O(n).Passaggio 2: Analisi dei cicli annidati
for j in range(n): for k in range(n): print(j, k)
Il ciclo esterno itera
n
volte e, per ogni iterazione, anche il ciclo interno iteran
volte. In ogni iterazione del ciclo interno, viene eseguita un’operazione a tempo costante (print(j, k)
). Pertanto, la complessità temporale dei cicli annidati è O(n * n) = O(n^2).Passaggio 3: Combinazione delle complessità temporali
La funzioneexample_function(n)
è composta da due passaggi: il primo ciclo e i cicli annidati. La complessità temporale complessiva è la somma delle complessità temporali di ogni passaggio.Complessità temporale del primo ciclo: O(n)
Complessità temporale dei cicli annidati: O(n^2)Per determinare la complessità temporale complessiva, consideriamo il termine dominante, che è il termine con il più alto ordine di crescita. In questo caso, O(n^2) domina O(n).
Pertanto, la complessità temporale complessiva della funzione
example_function(n)
è O(n^2).Nel caso peggiore, quando
n
è grande, i cicli annidati domineranno il tempo di esecuzione e la funzione avrà una complessità temporale quadratica.