Sfondo

• Per un loop for arbitrario come:

  for (int p = …; …)
      do_something(p);
  

  dovrebbe essere chiaro che il tempo di esecuzione di questo ciclo è semplicemente la somma dei tempi di esecuzione dei calcoli interni (cioè do_something(p) in questo caso). Nota che il tempo di esecuzione del calcolo interno può dipendere dalle variabili del ciclo.

  Nel caso speciale in cui il tempo di esecuzione di do_something(p) è indipendente dalle variabili di loop, il tempo di esecuzione è quindi proporzionale al numero di volte in cui viene eseguito il calcolo interno.

• In genere, le operazioni aritmetiche semplici come l'incremento ( sum++ ) sono operazioni a tempo costante.

• Per brevità userò log per indicare il logaritmo in base 2. Inoltre, userò pow(x, y) per indicare x elevato alla potenza y perché ^ è spesso usato per qualcos'altro nella famiglia di linguaggi C.

I problemi

L'interessante coincidenza in questo insieme di problemi è che il tempo di esecuzione di ciascun calcolo è in realtà proporzionale al valore finale del sum (puoi vedere perché?), quindi la domanda può essere semplificata: come fa il finale il valore di sum varia con il parametro N ?

Il sum può essere calcolato algebricamente, ma non è necessario conoscere il risultato esatto. Abbiamo solo bisogno di fare delle buone stime .

Problema A

int sum = 0;
for (int n = N; n > 0; n /= 2)
  for (int i = 0; i < n; i++)
    sum++;

Quante volte viene eseguito il ciclo esterno? Inizia a N e diminuisce della metà ogni volta finché raggiunge lo zero. Questa è solo una versione discreta di un decadimento esponenziale con una base di 2. Pertanto, possiamo fare un'ipotesi plausibile che

n ∝ 1 / pow(2, p)    [approximately]

Qui definiamo p come un contatore che aumenta di 1 ogni volta che il ciclo esterno viene ripetuto. In realtà, questo è esattamente ciò che il grafico traccia.

Dove inizia p ? Possiamo semplicemente scegliere p_start = 0 per comodità e questo ci consente di determinare il coefficiente di proporzionalità:

 n ≈ N / pow(2, p)

Dove termina p ? Ogni volta che n raggiunge zero! Poiché questa è una divisione intera, n può essere zero solo se N < pow(2, p) . Da ciò possiamo dedurre quel p_end ≈ log(N) (logaritmo in base-2). Con l'esperienza, puoi facilmente saltare l'intera analisi e passare direttamente a questa conclusione.

Ora possiamo riscrivere il ciclo usando la variabile p invece di n (di nuovo, approssimativamente ). Si noti che ogni istanza di n deve essere sostituita:

int sum = 0;
for (int p = 0; p < log(N); p++)
  for (int i = 0; i < N / pow(2, p); i++)
    sum++;

Il vantaggio di scrivere il ciclo in questo modo è che diventa ovvio quante volte viene ripetuto il ciclo esterno. (I lettori appassionati potrebbero notare che questo è

Il ciclo interno è costituito solo da incrementi a sum ed è ripetuto N / pow(2, p) volte, quindi possiamo semplicemente riscrivere quanto sopra a:

int sum = 0;
for (int p = 0; p < log(N); p++)
  sum += N / pow(2, p);

(Si noti che il tempo di esecuzione di questo ciclo potrebbe non essere più lo stesso, ma il valore di sum riflette ancora il tempo di esecuzione del problema originale.)

Da questo codice possiamo scrivere il valore di sum come:

(Come notato a caso, questa è solo una serie geometrica quindi c'è una forma chiusa ben nota espressione per la somma . Qui uso una tecnica più generale basata sul calcolo, comunque.)

Questo può essere ulteriormente semplificato approssimando la somma come integrale:

Ed ecco fatto, il tempo di esecuzione del problema A è lineare rispetto a N .

Problema B

int sum = 0;
for (int i = 1; i < N; i *= 2)
  for (int j = 0; j < i; j++)
    sum++;

Il problema qui è simile, ma tralascerò alcuni passaggi. La variabile i cresce esponenzialmente, quindi possiamo effettuare la trasformazione:

i ≡ pow(2, p)

con p che aumenta di uno ad ogni iterazione, a partire da 0 e termina a log(N) . Dopo la sostituzione variabile, il ciclo diventa:

int sum = 0;
for (int p = 0; p < log(N); p++)
  for (int j = 0; j < pow(2, p); j++)
    sum++;

che riduce a:

int sum = 0;
for (int p = 0; p < log(N); p++)
  sum += pow(2, p);

Puoi applicare nuovamente gli stessi trucchi per trovare un'espressione in forma chiusa per la somma: è anche O(N) .

Problema C

int sum = 0;
for (int i = 1; i < N; i *= 2)
  for (int j = 0; j < N; j++)
    sum++;

Questo è in realtà un po 'più semplice perché il numero di ripetizioni del ciclo interno non dipende dalla variabile del ciclo esterno, quindi possiamo andare subito e semplificarlo in:

int sum = 0;
for (int i = 1; i < N; i *= 2)
  sum += N;

Il ciclo ha lo stesso comportamento esponenziale del Problema B, quindi viene eseguito solo log(N) volte, quindi può essere semplificato in:

int sum = 0;
sum += log(N) * N;

Quindi, il tempo di esecuzione è O(N log(N)) .

Il tempo di esecuzione effettivo è meno importante della crescita del tempo di esecuzione in funzione degli input dell'algoritmo dalla prospettiva teorica dello studio degli algoritmi. Il mondo reale è tipicamente diverso.

Indipendentemente da ciò, il libro sta probabilmente discutendo dei tempi di esecuzione come un modo per illustrare diverse strutture di codice.

Un semplice esempio Java per il codice di temporizzazione è simile al seguente. Le lingue più popolari hanno un modo simile di realizzare la stessa cosa.

long begin = System.currentTimeMillis();
// Do some stuff
long interval = System.currentTimeMillis() - begin;
System.out.println("The algorithm took " + interval + "ms to process");

Utilizza questo linguaggio di programmazione per ogni struttura di codice che hai elencato e confronta i risultati. Sembra proprio quello che ti sta dicendo il libro.

Vista la velocità delle moderne CPU e l'efficacia dei moderni compilatori nell'ottimizzazione, ti consiglio di eseguire il ciclo di milioni di volte per ottenere un confronto accurato. Ciò significa che la variabile N nel tuo codice dovrebbe essere abbastanza grande. Vorrei anche eseguire ogni algoritmo più volte e prendere la media.

Il motivo è che c'è un sovraccarico associato a qualsiasi codice. Per avere un confronto accurato, assicurati di ridurre al minimo fattori come errori di cache .