小さいアルゴリズムからなるアルゴリズムの大きなo表記

Question

私はグラフを受け取り、グラフに余分な頂点を追加し、新しい頂点をソースとしてBellman Fordを適用してから、dijkstraのすべてのペアをグラフに適用します。

使用されているアルゴリズムは、次の実行時間/スペース要件を持っています。

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

.

私は全体のプロセスの大きなOを計算しているのであれば理解が難しいです。各プログラムは別々に実行され、出力はプログラムからプログラムに配置されます。私のけど全アルゴリズムは、

のビッグOランタイムを持つことになります。

O（V + EV + EVログV） o（ev log v）

スペース要件は同様の方法で計算されます。私はこれを正しく考えていますか？ありがとう！

Answer 1

正確に、「経験則」は、一連のコードブロックにおいて、全体的な複雑さが最大の複雑さ（漸近的に）

を超えるブロックによって支配されることです。

生殖成熟して、Vが非常に大きいほど大きくなると、EVよりも小さいため、EVLOGVよりも小さい。したがって、大きなVの場合、あなたのアルゴリズムの複雑さはevlogv

によってよく近似されます。