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 函数的乘积和集合的大小成比例地缩放。