Bonjour,
Pour le calcul de la complexité lors d'un pas de la simulation, devons-nous prendre le pire des cas ou la moyenne ?
Par exemple, d'après la documentation C++, la fonction push_back a un coût moyen en O(1), mais dans le pire des cas en O(n). Lequel doit être utilisé ?
Merci et bonne soirée
Hello Leane,
Thank you for the question.
As you might already know, the vector data structure as defined in C++ STL has a dynamic size unlike a standard array (it can shrink or extend at runtime). It is also allocated in a fixed memory space with a limited capacity even if the size is dynamic (check the capacity method in the vector). This result in the need of relocating the whole vector in larger memory region from time to time and copying all its elements to a new place. This copying operation is what cost O(n), but luckily, the need for reallocation and copying does not happen very often as the number of push_back operations; thus, we assume that the push_back has an amortized cost of O(1).
Ali
je confirme ce qu'Ali a déjà indiqué. De plus, pour les joueurs et les obstacles le nombre maximum est connu au début et peut être alloué en une seule fois avec la méthode reserve (cf sem1, topic12 slide 10):
https://moodlearchive.epfl.ch/2018-2019/mod/resource/view.php?id=877637
Seules les balles peuvent varier de manière plus dynamique, augmenter puis diminuer, en cours de partie. Un appel de la méthode reserve() peut aussi réduire le risque d'avoir des réallocations encours de partie.