Une complexité temporelle Big-Oh peut-elle contenir plusieurs variables?

Disons par exemple que je fais un traitement de chaîne qui nécessite une analyse de deux chaînes. Je n'ai aucune information sur leur longueur, ils proviennent donc de deux familles distinctes. Serait-il acceptable d'appeler la complexité d'un algorithme ou O (n + m) (selon que l'on utilise un algorithme naïf ou optimisé)?$O(n * m)$$O(n + m)$

Dans la même veine, supposons que l'algorithme que nous choisissons nécessite en réalité deux étapes - une phase de configuration sur la première chaîne qui nous permet de traiter un certain nombre d'autres chaînes sans encourir ce coût initial. Serait-il approprié de dire qu'il a une construction $O(n)$ suivie d'un nombre quelconque de calculs $O(m)$ ?

Serait-il approprié de simplement les appeler $O(n)$ parce que les deux calculs sont linéaires?

Oui bien sûr. C'est bien et parfaitement acceptable. Il est courant et standard de voir des algorithmes dont le temps d'exécution dépend de deux paramètres.

Par exemple, vous verrez souvent le temps d'exécution de la recherche en profondeur d'abord exprimé en , où est le nombre de sommets et est le nombre d'arêtes dans le graphique. C'est parfaitement valable. La signification de ceci est qu'il existe une constante et des nombres tels que le temps d'exécution de l'algorithme soit au plus , pour tout . En d'autres termes, si le temps de fonctionnement exact est , on dit que s'il existe tels que et impliquen m c n 0 , m 0 c ⋅ ( n + m ) n > n 0 , m > m 0 f ( n , m ) f ( n , m ) = O ( n + m ) c , n 0 , m 0 n > n 0$O(n+m)$$n$$m$$c$$n_0,m_0$$c \cdot (n+m)$$n>n_0,m>m_0$$f(n,m)$$f(n,m) = O(n+m)$$c,n_0,m_0$$n>n_0$$m>m_0$$f(n,m) \le c \cdot (n+m)$ .

Oui, il est parfaitement approprié et acceptable de dire que le premier étage prend le temps et le deuxième étage prend le temps .$O(n)$$O(m)$

Important: assurez-vous de définir ce que sont et . Vous ne pouvez pas dire "ceci est un algorithme de temps " sans spécifier ce que est. Si n'est pas spécifié dans l'énoncé du problème, vous devez le spécifier. Par exemple, voir les algorithmes de graphe, où nous définissons généralement # de sommets et # d'arêtes.$n$$m$$O(n)$$n$$n$$n =$$m =$

Quant à savoir si vous pouvez les appeler temps , non, bien sûr que non - à moins que vous ne sachiez en quelque sorte que . Bien sûr, si vous savez que , il s'ensuit que , donc un algorithme de temps est également un algorithme de temps . Mais s'il n'y a aucune garantie que , alors vous ne pouvez pas l'appeler un algorithme de temps .m = O ( n ) m = O ( n ) m + n = O ( n ) O ( m + n ) O ( n ) m = O ( n ) O ( n $O(n)$$m = O(n)$$m = O(n)$$m+n = O(n)$$O(m+n)$$O(n)$$m = O(n)$$O(n)$

Ce sont des trucs de base. Vous le trouverez partout dans les manuels d'algorithmes.