Calculer le temps de fonctionnement en utilisant des échantillons

Question

Supposons que vous chronométrez un programme en fonction de N et que vous produisiez le tableau suivant :

        N   seconds
-------------------
     4096      0.00
    16384      0.01
    65536      0.06    
   262144      0.51   
  1048576      4.41   
  4194304     38.10  
 16777216    329.13  
 67108864   2842.87

Estimez l'ordre de croissance du temps de fonctionnement en fonction de N. Supposez que le temps de fonctionnement obéit à une loi de puissance T(N) ~ a N^b.

Answer 1

Vos N sont tous des puissances consécutives de 4. En prenant le logarithme basé sur 4 des rapports consécutifs de temps, vous verrez qu'ils convergent vers une certaine constante connue sous le nom de "b". Lorsque vous substituez N, T(N) et b de la dernière entrée de votre tableau à la loi de puissance (T(N) = a * N ^ b), vous obtenez 'a'. Dans votre cas, le log4 des rapports de temps converge vers 1,555, c'est donc 'b'.

Je suppose que vous suivez le cours "Algorithmes, partie I" de Coursera (comme moi). Alors, ce fil de discussion doit être disponible pour vous :

https://class.coursera.org/algs4partI-002/forum/thread?thread_id=149

Vous pouvez également vous référer aux diapositives "Analyse des algorithmes" à partir de la page 16.

Answer 2

Vous devez utiliser un graphique logarithmique (logN), puis prendre la pente de la ligne. Cela indiquera l'exposant b.

Answer 3

Vous pouvez calculer la pente entre chaque deux échantillons pour l'ensemble de la série d'échantillons. Vous pouvez ensuite le faire de manière récursive (pente des pentes). Cela devrait vous donner b

Answer 4

Utilisez la loi de puissance de l'ajustement des moindres carrés :

http://mathworld.wolfram.com/LeastSquaresFittingPowerLaw.html

Vous obtiendrez ainsi l'ajustement le plus proche pour a et b, que vous pourrez ensuite utiliser pour extrapoler la durée d'exécution de nouveaux points.

Answer 5

Pour moi, c'est plus clair de cette façon :

N           seconds     log(N, 2)   log(seconds, 2)  Y(n)-Y(n+1)/
                            or X     or Y            X(n)-X(n+1)
----------------------------------------------------------------------------
4096              0         12      #NUM!
16384          0.01         14      -6.64385619         1.29248125
65536          0.06         16      -4.058893689        1.543731421
262144         0.51         18      -0.9714308478       1.556104752
1048576        4.41         20      2.140778656         1.555470218
4194304        38.1         22      5.251719093         1.555397315
16777216     329.13         24      8.362513723         1.555309345 
67108864    2842.87         26      11.47313241

La réponse : b est approximativement 1.55

Estimez l'ordre de croissance du temps d'exécution en fonction de N. C'est la version google drive...