Grande efficacité O pour plusieurs variables

Question

J'essaie d'évaluer l'efficacité d'une fonction où l'entrée est un tableau de chaînes. L'algorithme parcourt toujours chaque élément de ce tableau. Ces chaînes contenues dans ce tableau sont de longueur variable. Dans cette boucle for initiale, une fonction de remplacement de caractère est appelée sur chaque chaîne. Je crois que la fonction de remplacement en elle-même serait O (n) où n est la longueur de la chaîne.

Donc, je suis confus comment évaluer une grande efficacité ici. Si n est la taille du tableau, je sais qu'il sera au moins O (n). Mais avec des longueurs de corde variables, comment évalueriez-vous l'efficacité globale avec le remplacement de la chaîne? Diriez-vous que n est la taille du tableau et utilise d'autres variables pour représenter les différentes tailles de chaque chaîne?

Answer 1

Je vois deux façons de dire cela (sur beaucoup de possibles).

La première est de dire O(N) où N est le nombre total de caractères.

L'autre que vous pourriez dire est O(N*M) où N est le nombre de chaînes et M est le nombre moyen de caractères par chaîne. Notez que c'est en fait la même chose que ma réponse ci-dessus. Vous pouvez dire M = k/N, donc vous obtenez O(N*k/N) ou O(k) où k est le nombre total de caractères dans toutes les chaînes.

Answer 2

Personnellement, je voudrais exprimer l'efficacité à travers taille des données d'entrée (par opposition à la longueur de la matrice). Donc, si l'entrée est t octets, le temps d'exécution sera O(t). Et t ici est également une longueur commune de toutes les chaînes.