Supposons que pour un entier N donné, je dois exécuter une racine carrée de boucle de N fois.
En C ++, je peux le faire de deux manières comme-
1) p >
for (long long i=1; i * i < N; i++) {
// some same piece of code
}
long long sqrtN = std::sqrt(N);
for (long long i=1; i < sqrtN; i++) {
// some piece of code
}
J'ai trouvé que std :: sqrt () avait une complexité O (logn). De plus, je pense que la multiplication des nombres est juste une opération à temps constant.
Donc, on a l'impression que la 2ème version est plus rapide. Mais, pour une très grande valeur de n, ce temps constant dans la 2ème version peut être significatif.
Ainsi, je ne suis pas vraiment sûr de la manière la plus efficace?
3 Réponses :
J'ai trouvé que std :: sqrt () avait une complexité O (logn). De plus, je pense que la multiplication des nombres n’est qu’une opération à temps constant.
Jusqu'ici tout va bien. Vous avez manqué un détail. Dans le premier, vous appelez sqrt une fois, dans le second, vous calculez i * i dans chaque itération de boucle. Il s'agit donc en fait de O (log n) vs O (sqrt (n)) , c'est-à-dire que le calcul de la limite en dehors de la boucle gagne car log n
Pour vraiment savoir ce qui est le plus efficace, la complexité asymptotique ne peut que vous donner un premier indice sur ce qui se passe lorsque vous augmentez n jusqu'à l'infini. Pour un cas réel, vous devriez regarder la sortie du compilateur et du profil.
Je ne saurais trop insister sur le fait que la complexité présente principalement un intérêt théorique. Pour le vrai code, il n'y a aucun moyen de contourner le profilage et la mesure. Il n'est pas improbable qu'un algorithme O (N) l'emporte sur un algorithme O (logN) , car la complexité asymptotique ignore complètement les facteurs constants.
PS: ne faites pas d'optimisation prématurée. Écrivez du code pour plus de lisibilité et laissez les optimisations à votre compilateur. Ce n'est que si vous avez mesuré et constaté que trop de temps est passé pour calculer la limite de la boucle que vous devez faire quelque chose. Considérez que i * i est une seule instruction alors que le corps de votre boucle est probablement bien plus que cela (cf. loi d'Amdahls).
Je pense que vous avez déjà répondu vous-même à la plupart de vos questions:
N a une complexité de O (Log (N)) i peut être assez rapide, mais vous devez le faire sqrt (N) fois, et par conséquent la complexité est plus grande que O (sqrt (N)) . Comme O (Log (N)) est plus petit que O (sqrt (N)) , je dirais que la première approche est la plus rapide.
Pensez-y de cette façon - le calcul de la racine carrée ne se produit qu'une seule fois. Cette heure est essentiellement masquée lorsque vous exécutez la boucle plusieurs fois. La quadrature, cependant, a une complexité linéaire avec le nombre d'itérations de boucle, c'est-à-dire O (sqrt (N)), et sera plus lente pour les grands N.
pourquoi ne pas lancer de benchmark?
sqrtne peut être qu'une seule instruction d'assemblage, commesqrtsd.@Evg: ... qui peut encore être très cher. Le nombre d'instructions de montage n'est pas un bon indicateur de performance.
@DevSolar, d'accord. Le fait était que
sqrt (n)n'est pas nécessairementO (log n).Notez également que
++ iest plus rapide quei ++. ;-)@Caduchon: Non, pas vraiment. Voir Y a-t-il une différence de performances entre i ++ et + + i en C?
@FabiosaysReinstateMonica ouais. Mais pas pour les itérateurs. Dans ce cas, c'est pareil.