Stima del tempo di esecuzione dell'algoritmo

Le classi di complessità come O(n) o O(n²) non sono pensate per calcolare il tempo di esecuzione effettivo. Invece, hanno lo scopo di confrontare il modo in cui i diversi algoritmi si ridimensionano quando cambiamo le dimensioni dell'input.

Ad esempio, qui abbiamo due algoritmi che applicano frobnicate(a, b) a ciascun elemento corrispondente:

void algorithm1(Set<int> items) {
  for (int i in items) {
    for (int j in items) {
      if (i == j) {
        frobnicate(i, j);
      }
    }
  }
}

void algorithm2(Set<int> items) {
  for (int i in items) {
    frobnicate(i, i);
  }
}

Ovviamente, il primo algoritmo ha una complessità di O(n²) mentre il secondo è di O(n) . Pertanto, possiamo concludere che algorithm2 scala meglio per i grandi input. Ma ecco un altro algoritmo O(n) :

void algorithm3(Set<int> items) {
  sleep(9 seconds);
  for (int i in items) {
    sleep(1 millisecond);
    frobnicate(i, i);
  }
}

Questa scala è uguale a algorithm2 ma sarà sempre più lenta! Infatti, O(n²) algorithm1 supererà questo algoritmo per piccoli input! Poiché algorithm3 ha un overhead fisso di 9 secondi, non possiamo inserire numeri diversi nella formula di complessità di O(n) per scoprire quanto tempo impiegherà una dimensione di input diversa.

Esempio:

n=1000 => algorithm3 takes 10 seconds
n=2000 => algorithm3 takes 11 seconds, not 20 seconds!

In realtà, il tempo di esecuzione non è possibile calcolare in modo affidabile. Anche se riesci a calcolare un costo per ogni operazione atomica, le stranezze hardware come i limiti della cache ti ostacoleranno. L'unica opzione affidabile consiste nell'eseguire il campionamento statistico su diverse dimensioni di input e quindi adattare una funzione di stima che corrisponda alla classe di complessità prevista ai dati raccolti.

Supponiamo di avere una funzione di stima del tempo di esecuzione (! = classe di complessità) di f(n) = a·n² + b·n + c , e assumiamo che b = c = 0 per semplicità (cioè senza fattori lineari, nessun sovraccarico costante). Quindi, possiamo calcolare il parametro a dal punto dati f(1000) = 10 seconds :

10 seconds = f(1000)
           = a·1000²
           = a·1000000
 <=> a = 10/1000000 seconds = 1/100000 seconds

Pertanto, f(n) = n²/100000 seconds . Se inseriamo n = 2000 , otteniamo

f(2000) = 2000²/100000 seconds
        = 4000000/100000 seconds
        = 40 seconds

Questo è coerente con la scorciatoia che se moltiplichiamo la dimensione di input per n (qui n = 2 ), l'output è aumentato di n² (qui n² = 4 ).

Per farla breve:

La prima frase della risposta di amon è importante.

Ma anche la tua ipotesi è corretta: 1000^2 è 4 volte superiore a (2*1000)^2 . Cioè se 1000^2 è uguale a 10 secondi su un determinato hardware, allora (2*1000)^2 è uguale a 40 secondi. È semplicemente la regola del tre.

Un'altra nota: se hai a che fare con il tempo di esecuzione dell'implementazione di un algoritmo, dovresti anche testare le prestazioni della tua implementazione. Gli "errori" di programmazione semplici possono fare un'enorme differenza nel mondo reale.