python - random.sample 的时间复杂度

Question

在另一个线程中，我看到二进制堆加权随机样本的时间复杂度等于 O(n * log(m))，其中 n 是选择数，m 是可供选择的节点数。

我想知道 Python 用作 random.sample 的未加权随机样本的时间复杂度。时间复杂度只是 O(n) 还是完全不同？

Answer 1

Python 源代码：（random.py第 267 行）。

这是相关的位：

   315             selected = set()
   316             selected_add = selected.add
   317             for i in range(k):
   318                 j = randbelow(n)
   319                 while j in selected:
   320                     j = randbelow(n)
   321                 selected_add(j)
   322                 result[i] = population[j]

它基本上将随机索引“掷骰子”到population. 如果它得到一个已经在 set 中的索引selected，它会重新滚动。冲洗、起泡和重复k次数（k您要求的样品数量在哪里。）

它似乎O(n)在所请求的样本数量的大小中。小型集合有一些优化，但最重要的是上面的主循环。

---

编辑：

我相信第 305-313 行是一个特殊情况，因为当请求的样本数量k占总人口的很大一部分时n。我们不是从整个种群中滚动随机元素（如果我们与已经选择的元素发生碰撞则重新滚动），我们明确地维护一个我们尚未选择的元素列表。我们保证每次都会得到一个新元素，但代价是我们必须维护列表。

如果我解释错了，请随时在下面发表评论。

   303         result = [None] * k
   304         setsize = 21        # size of a small set minus size of an empty list
   305         if k > 5:
   306             setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
   307         if n <= setsize:
   308             # An n-length list is smaller than a k-length set
   309             pool = list(population)
   310             for i in range(k):         # invariant:  non-selected at [0,n-i)
   311                 j = randbelow(n-i)
   312                 result[i] = pool[j]
   313                 pool[j] = pool[n-i-1]   # move non-selected item into vacancy
   314         else:
   315             selected = set()
   316             selected_add = selected.add
   317             for i in range(k):
   318                 j = randbelow(n)
   319                 while j in selected:
   320                     j = randbelow(n)
   321                 selected_add(j)
   322                 result[i] = population[j]
   323         return result

Answer 2

来源：https ://hg.python.org/cpython/file/ab500b297900/Lib/random.py

这个答案类似于上面 Li-aung Yip 的答案，但我认为精度对于某些应用程序可能很重要。

对于一个大小的总体n和一个大小的样本k，复杂性可能会受到总体输入类型的影响：如果总体是一个集合，则 random.py 的第 296行将其复制到一个元组，即O(n)什么是n或k。如果是序列，则无需预处理。

之后，如果k足够大（见下文），则 random.sample 使用以下循环（random.py 的第 305-313 行），这O(n)又是因为人口的副本。

    if k > 5:
        setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
    if n <= setsize:
        # An n-length list is smaller than a k-length set
        pool = list(population)
        for i in range(k):         # invariant:  non-selected at [0,n-i)
            j = randbelow(n-i)
            result[i] = pool[j]
            pool[j] = pool[n-i-1]   # move non-selected item into vacancy

与 不同的平均情况复杂度的唯一希望O(n)是 whenk足够小，以至于使用以下循环：

else:
    selected = set()
    selected_add = selected.add
    for i in range(k):
        j = randbelow(n)
        while j in selected:
            j = randbelow(n)
        selected_add(j)
        result[i] = population[j]

这似乎是O(k)一般情况，但我不确定如何证明这一点。如果我犯了错误，请随时发表评论。