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