Règle de somme pour Big-o avec des fonctions de complexité égales?
-
29-09-2020 - |
Question
Une propriété de la big-o-notation est le SUM RÈGLE , lequel stipule que lorsque j'ai deux fonctions $ f_1 $ et $ f_2 $ et leurs fonctions de complexité correspondantes sont $ g_1 $ et $ g_2 $ , alors la complexité combinée est $ F_1 + F_2= O (\ max (g_1, g_2)) $ .
Mais que choisissez-nous si les deux fonctions de complexité sont égales? Par exemple, si $ f_1 (n) $ est le tri d'une matrice et $ _ f2 (m) $ En outre, alors les complexités sont $ O (n \ journal (n)) $ et $ o (m \ log ( m)) $ . L'application de la règle serait $ O (\ max (n \ journal (n), m \ journal (m))) $ . Je pense que la sélection de ceux-ci céderait une estimation valide mais très non intuitive, car vous laisseriez une variable. En plus de cela, ce n'est pas clair lequel choisir.
est-ce que vous n'êtes pas censé utiliser la règle lorsqu'il y a plusieurs variables impliquées?
La solution
Cela dépend de si certaines variables dépendantes d'une autre, ou si elles sont données comme paramètres dans le problème. Par exemple, dans de nombreux problèmes liés au graphique, $ n $ peut être le nombre de sommets et $ m $ peut être le nombre de bords. Dans ce cas, $ m $ peut être aussi grand que $ o (n ^ 2) $ . Donc, dans le cas général, disons si nous avons un algorithme dont la première phase fonctionne dans $ o (n) $ et deuxième phase dans $ O (m) $ , nous ajoutons simplement les deux termes ensemble et n'essayez pas de simplifier --- L'exécution finale est $ O (n + m) $ .
En termes de plusieurs variables données en tant que paramètres qui ne sont pas nécessairement liés: l'espérance de plusieurs variables à l'intérieur de l'équation finale est standard, par exemple. Je peux dire que multiplier une $ m \ fois n $ matrice et une $ n \ fois p $ matrice prend $ o (mnp) $ -temps en utilisant la multiplication de l'écolier ou la résolution du problème du knapsack prend $ o (nt) $ < / span> -time où $ n $ est le nombre d'éléments et $ t $ est la somme cible .
Dans des cas spéciaux tels que des graphiques planaires et d'autres graphiques rares, nous savons que $ m= o (n) $ , nous pouvons donc substituer en toute sécurité N $ N $ à la place de $ m $ dans la dernière heure de fonctionnement pour la simplification.
comme une digression, cela illustre pourquoi sur les graphiques rares (où $ m= o (n) $ ) on préférerait utiliser Dijktra's dans une boucle pour tout- paires de chemins les plus courts (contrairement à un algorithme basé sur la fermeture transitive comme Floyd-Warshall); Etant donné que maintenant Dijkstra fonctionne dans $ O (m \ journal n)= O (n \ journal n) $ , la complexité globale pour l'utilisation de Dijkstra dans une boucle devient $ O (n ^ 2 \ journal n) $ , ce qui est meilleur que Floyd-Warshall. En revanche, notez que Dijkstra est exécutée dans $ m \ journal n $ pour le cas général, ce qui signifie sur des graphiques denses où $ m= o (n ^ 2) $ , il devient moins efficace que Floyd-Warshall en termes de temps de fonctionnement du pire des cas.
Dans d'autres cas, il peut y avoir des variables ne sont même pas bornées polynomentiellement par un paramètre donné - prennent l'exemple de sacs à dos ci-dessus, où $ t $ peut être exponentielle dans $ n $ .
Autres conseils
Il n'y a pas de réponse générale.Au fait, si vous voulez simplifier la $ O (\ max (n \ journal (n), m \ journal (m))) $ , vous pouvez réécrirec'est comme $ o ((n + m) \ journal (n + m)) $ .
d'ailleurs, si $ g_1 $ et $ g_2 $ est Eqaul et des fonctions croissantes, vous pouvez écrire $ O (g_1 (n + m)) $ au lieu de $ o (\ max (g_1 (n), g_2 (m)))) $ .
par définition $ o (g) $ doit être toujours défini de point variable et de point limite en ce qui concerne l'envisage de $ o $ . Par exemple dans $ O (N ^ 3), N \ to \ \ PLAND $ La variable est $ n $ et Point limite $ \ \ € $ . Dans $ o (x ^ 3), x \ à 0 $ variable est $ x $ et point limite $ 0 $ .
Alors, quand nous écrivons $ f= o (g) $ , puis formellement, nous entendons une variable et un point limite. Par exemple $ F (N)= O (g (N)), n \ to \ to \ € / span> est un enregistrement exact. Remarque, cet enregistrement $ f (m)= O (g (m)), m \ to \ to \ g $ signifie exactement comme la phrase précédente.
Quand nous parlons de la propriété $ f_1 + f_2= o (\ max (g_1, g_2)) $ , alors ici doit également être indiqué à une variable (S ) et un point limite. Un enregistrement si exact devrait être quelque chose comme $$ f_1 (n) + f_2 (n)= O (\ max (g_1, g_2) (n)), n \ to \ to \ £ $$ Ou nous avons besoin de plus de clarification en ce qui concerne les variables, en supposant que le point limite $ \ g $ .