je voudrais pas vous décevoir, mais après un rapide coup d´œil aux sources de PHP, appeler str_replace avec un tableau de chaine à remplacer, c´est comme l´appeler une fois avec chacune des chaines. Le résultat est exactement le mêle (en tout cas, à ce que j´ai compris, car les sources ne sont pas limpide). (Cf fonction php_str_replace_in_subject dans ./ext/standard/string.c dans les sources de PHP).
Dans tout les cas, même si la chaine était parcourue de bout en bout une seule fois, mais chaque caractère lu plusieurs fois (une pour chaque chaine à remplacer, pour voir si ça colle), et que l´on a une chaine de longueur n, avec m chaines à rechercher pour faire des remplacement (et de longueur bornée et petite), alors en parcourant m fois la grande chaines, ou une fois, mais en comparant chaque caractère, on a la même complexité en O(m*n).
Pour faire mieux, il faut construire un automate qui parcourt la chaine, à la recherche des sous chaine. Lui, il peut se contenter de lire une seule fois chaque caractère de la chaine d´entrée. Mais je ne crois pas que PHP fasse cela ...
bon, c´était la minute enculage de mouche. Mais puisque j´ai perdu du temps à regarder comment fonctionne PHP, je me suis dit que j´allais vous en faire profiter.