Règle de somme pour Big-o avec des fonctions de complexité égales?

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?

Answer 1

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 $ .

Answer 2

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)))) $ .

Answer 3

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 $ .