Big O Notation do Algoritmo composto de pequenos algoritmos

Question

Eu estou trabalhando em uma atribuição que leva alguns você pode encontrar um gráfico, adiciona mais uma vértice para o gráfico, aplica-se Bellman Ford com o novo vértice como a fonte e, em seguida, usa aplica-se Dijkstra todos os pares para o gráfico.

Os algoritmos usados tempos de execução de espaço/requisitos:

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

Estou tendo dificuldade de entender se eu sou o cálculo do big O do processo total.Cada programa é executado separadamente, e o de saída é encaminhado de programa para programa.O meu que é o total do algoritmo teria um Big-O tempo de execução de:

O( V + EV EV log V ) qual seria simplificar a O EV( log V )

O requisito de espaço deve ser calculado de forma semelhante.Estou eu a pensar isso corretamente?Obrigado!

Answer 1

Exatamente, uma "regra de ouro" é que, em uma seqüência de blocos de código, a complexidade total é dominada pelo bloco com maior complexidade (assintoticamente)

Matematicamente, quando V tende para números muito grandes, é menor do que o EV, que é menor do que EVlogV.Assim, para a grande V, a complexidade do algoritmo é aproximada assim por EVlogV