Big O notation d'algorithme composé d'algorithmes plus petits

Question

Je travaille sur une affectation qui prend un graphique, ajoute un sommet supplémentaire au graphique, s'applique Bellman Ford avec le nouveau sommet comme source, puis utilise applices toutes les paires de dijkstra sur le graphique.

Les algorithmes utilisés ont des exigences d'exécution / espace de:

Adding extra vertex
-- Running Time: V
-- Space: V
Bellman Ford single source shortest path algorithm
-- Running time: EV
-- Space: V
Dijkstra's all pairs shortest path algorithm
-- Running time: EV log V
-- Space: V

J'ai des difficultés à comprendre si je calcule le gros o du processus total.Chaque programme est exécuté séparément et la sortie est devenu du programme au programme.Ma bien que l'algorithme total aurait une période d'exécution Big-O de:

O (v + ev + ev journal v) qui simplifierait O (EV log V)

L'exigence spatiale serait calculée de manière similaire.Je pense à cela correctement?Merci!

Answer 1

Exactement, une "règle de base" est que, dans une séquence de blocs de code, la complexité globale est dominée par le bloc avec la plus grande complexité (asymptotiquement)

Matimatiquement, lorsque v tendance à de très grands nombres, il est plus petit que EV, qui est plus petit que EvlogV.Ainsi, pour le grand V, la complexité de votre algorithme est approximativement par evlogv