singolo problema di spiegazione runtime for-loop

Naviga le tue risposte
8

Sto analizzando alcuni tempi di esecuzione di diversi cicli di apertura e, poiché sto acquisendo più conoscenza, sono curioso di capire questo problema che devo ancora scoprire. Ho questo esercizio chiamato "Quante stelle sono stampate": 

for (int i = N; i > 1; i = i/2) System.out.println("*");

Le risposte tra cui scegliere sono A: ~log N B: ~N C: ~N log N D: ~0.5N^2

Quindi la risposta dovrebbe essere A e sono d'accordo, ma dall'altra parte .. Diciamo N = 500 cosa sarebbe Log N quindi? Sarebbe 2.7. Quindi, cosa succede se diciamo che N=500 sul nostro esercizio sopra? Questo sicuramente stamperebbe più di 2,7 stelle? Com'è collegato?

Perché ha senso dire che se il ciclo for ha questo aspetto: 

for (int i = 0; i < N; i++)

stamperebbe N stelle.

Spero di trovare una spiegazione per questo qui, forse sto interpretando tutte queste cose sbagliate e pensandoci male. Grazie in anticipo.

    
posta owwyess 18.08.2014 - 14:32
fonte

2 risposte

34

Hai trascurato le caratteristiche chiave della base del logaritmo .

Poiché i è diviso per 2 in ogni iterazione, il tempo di esecuzione è logaritmico con base 2. E

log2(500) ~ 8.9

Quello che stai guardando è

log10(500) ~ 2.7

(logaritmo con base 10)

A proposito, il motivo per cui la base viene spesso omessa nelle discussioni in runtime (e probabilmente la tua calcolatrice non ha un pulsante per log 2 ) è dovuto ai meccanismi della matematica logaritmica, una base diversa corrisponde a un fattore costante e quindi non è rilevante quando si ignorano comunque i fattori costanti. Può essere calcolato facilmente:

loga(x) = logb(x) / logb(a)

    
risposta data 18.08.2014 - 14:39
fonte
8

Oltre alla risposta di Michael Borgwardt , il carattere tilde di fronte a ogni risposta deve essere letto come "proporzionale" a". Quindi se raddoppi N (per esempio, da 500 a 1000), vedresti che il tempo di esecuzione (o, in questo caso, il numero di stelle stampate) aumenterebbe di un fattore che sarebbe uguale a (log1000 / log 500), che è indipendente da quale base si utilizza.

    
risposta data 18.08.2014 - 19:43
fonte

Leggi altre domande sui tag

Ci sono ancora aziende / centri accademici che usano i mainframe degli anni '60 -'70? [chiuso] Perché la funzione di stampa più semplice di C è denominata 'print' anziché 'printf'? [duplicare]