Quando n diventa grande, delle due funzioni log * (log n) e log (log * n) sarà più veloce?Quale registro dei tassi di crescita (log * n) e log * (log n) è più veloce?
Qui, il registro * funzione è il logaritmo iterato, definito qui:
ho il sospetto questi sono gli stessi, appena scritto in modo diverso, ma c'è qualche differenza tra loro?
log * n è il iterated logarithm, che per n grande è definita come
log* n = 1 + log*(log n)
Pertanto, log * (log n) = (log * n) - 1, poiché registro * è il numero di volte è necessario applicare il registro al valore prima che raggiunga una costante fissa (in genere 1). Fare prima un altro registro rimuove solo un passaggio dal processo.
Pertanto, log (log * n) sarà molto più piccolo di log * (log n) = log * n - 1 poiché log x < x - 1 per ogni x ragionevolmente grande.
Spero che questo aiuti!
wow. bella risposta lì! ;) –
se i tuoi asterischi hanno lo scopo di indicare "logstar", ovvero n log n, potresti voler riscriverlo in questo modo, perché SO li ha analizzati in un modo che immagino tu non intendessi – mfrankli
log * non è n log n. – templatetypedef
buona chiamata, non ho idea di dove l'ho ottenuto da – mfrankli