sujet de l'X SPé info caml différence sym liste O(m+p)

[invitef1ec1449]

bonjours j'ai un ptit pb avec un sulet d'info de l'X, ds une question qui demande de faire une fonction qui effectue la différence symétrique entre deux listes; on precise que le nombre d'opération ne devra pas depasser O(m+p) où m et p sont les cardinaux des argument; est ce que qq un pourrait m'expliquer ce qu'est ce O(m+p)?

Merci d'avance
-----

[invite9c9b9968]

Tiens c'est marrant je crois que c'était le sujet de mon année

O(m+p) c'est la complexité de l'algo, ça veut dire que le nombre d'opération doit être de l'ordre de (m+p), ou plus précisément si je note A le nombre d'opération, j'ai A/(m+p) borné si je fais tendre (m+p) vers l'infini.

[inviteec31acba]

Ce qui représente la complexité la plus faible possible pour ce genre de résolution. Ce qui "prouve" que ton algo est le meilleur à l'ordre près et donc que tu n'as pas construit une "usine à gaz" autrement dit qu'il est le plus "optimisé". Cela sera une méthode de vérification pour toi, une fois construite ta fonction, tu pourras vérifer qu'il n'en existe pas 'de plus rapide'.