1

時間の複雑さO(v+e)は、プログラムで別々に実行される 2 つのループ (e 回と v 回) に似ていることは明らかです。

しかし、同じことが空間の複雑さになると、私は混乱します。

O(v)最初にスペースを割り当ててから解放し、次にスペースを割り当てるようなものO(e)ですか?

ありがとう！

4

1 に答える 1

5

時間の複雑さを扱っている場合、加算 ( O(v+e)) は 2 つのことが連続して起こっていることを意味します。空間の複雑さに移行する場合、+記号は時間ではなく空間のコンテキストで使用する必要があります。

O(v+e)スペースを使用するのと同等のO(v)+O(e)スペース。基本的に（ここではグラフを扱っていると仮定しています）、各頂点にいくつかのストレージスペースを使用し、各エッジにいくつかのスペースを使用していることを意味します（おそらく aList<Vertex>と a List<Edge>、または何かがあります）-おそらくすべて同時に。

O(v)メモリの割り当て、解放、およびメモリの割り当ての例では、いつでもスペースをO(e)使用しています。O(max(v,e))

編集: G. バッハが指摘したように、O(v+e)は常に と同等O(max(v,e))です。どちらか一方が明確さの点でより適切である場合があると私は主張します（どちらか一方が実際に使用されている空間/時間をより適切に表現します）が、それは主観的です. これがクラス用の場合、講師はどちらか一方の表記法を好む可能性があります - クラスノートから明らかである必要があります。しかし、要するに、O(v+e)説明されている両方の状況に適しています。

于 2013-08-12T12:48:43.247 に答える