Sono un principiante degli algoritmi. Una cosa che mi confonde sempre riguarda il calcolo dei runtime degli algoritmi. Ad esempio: il seguente pezzo di codice in Python
for i in range(n):
#O(?)
i*=k
Qual è il tempo di esecuzione del ciclo precedente? La risposta che mi è stata fornita è: O (registra n alla base k).
Sto trovando difficile capire come sia arrivato questo runtime.
Qualsiasi hep sarebbe molto apprezzato.
Il tempo di esecuzione di un algoritmo è spesso espresso in funzione della sua complessità. Nel tuo esempio, puoi pensare a "runtime" come "il numero di passaggi". La complessità è O( log( n, k ) ) , secondo la tua fonte.
Quando n è 20 e k è 3 , quanto è log( n, k ) ? Dovrebbe essere log( 20, 3 ) che è circa 2.72 .
Quanti passaggi ha il tuo algoritmo? Se stampi i tuoi valori su ciascun ciclo dovresti vedere qualcosa del tipo:
i = 0, i*k = 0
i = 1, i*k = 3
i = 4, i*k = 12
i = 13, i*k = 39
Quindi, ci sono voluti quattro passaggi per eseguire l'algoritmo. Chiaramente c'è un disaccordo tra 3 (arrotondato per eccesso da 2.72) e 4.
Guardando la tua dichiarazione dell'algoritmo, sospetto che il codice Python avrebbe dovuto essere dichiarato come segue:
k = 3
n = 20
i = 1
while i <= n:
print "i =", i, "i*k =", i*k
i = i*k
i = i+1
Questo algoritmo mostrerà solo tre passaggi, corrispondenti alla complessità stimata.
Dovresti notare che la tua dichiarazione originale del codice Python è errata perché sta modificando la variabile di controllo di iterazione, i , nel mezzo del ciclo. Tali pratiche porteranno alla confusione e agli errori e sono strongmente scoraggiate.
Leggi altre domande sui tag big-o algorithm-analysis