graph - 確率はO（m）に等しい

Question

nがネットワークのサイズであるとしましょう。

mはnの関数です。

n個のノードからノードのサブセットを作成します。ノードの確率はp=O（m）です。

p = O（m）とはどういう意味ですか、与えられた確率に基づいてn個のノードからサブセットを作成するにはどうすればよいですか。

ありがとうございました。

Answer 1

単一ノードの確率はO（m（n））です。したがって、この条件を満たすには、サブセットにO（m（n）* n）ノードが存在する必要があります。これは、サブセットサイズがm関数とセットのサイズの積に比例してスケーリングすることを意味します。