Big-O计算复杂度：用dumb算法从总共n个元素中抽取一个非冲突的k个元素子集

Question

我想了解这个伪代码的计算复杂性：

values is a set of n unique elements
subset is an empty set
for 0 ... k
    X: randomly select a value from values
       if value is in subset
           goto X
       else
           insert value into subset

这当然是一个（糟糕的）算法，用于从 n 个元素中选择 k 个元素的唯一随机子集，我知道更好的选择，但我想了解它的计算复杂性。

我可以很容易地看出，当允许重复时，这是 O(n)，因为从伪代码中删除了条件测试，并且每次都做出 k 个选择。

当您必须考虑重复项时，需要重新测试的可能性会随着每次迭代而增加。根据 n 和 k 的值，这是一个不可忽视的事实，但我不确定它如何以一般方式影响 big-O 复杂性。有人可以给我解释一下吗？

Answer 1

对于每个k值，将值插入子集的概率是(n-k)/n

每k次循环的迭代次数与该概率成反比

因此，每个 k 值的大 O 表示法将是 O((n/(n-K)) + 1)，其中 1 将是 'insert value into subset'。

你必须计算每个 k 值的 ((n/(n-K)) + 1) 的总和——最终答案是 O(((n/(n-K)) + 1) 对于 k 从 1 到 k)

免责声明 - 这是假设 Big(o) 是否适用于使用随机数生成算法的函数（因为 X 是随机的）

Big-O计算复杂度：用dumb算法从总共n个元素中抽取一个非冲突的k个元素子集

Big-O complexity of calculation: Drawing a non-colliding subset of k elements from n total with dumb algorithm

complexity-theory

probability