只要总和小于 1，随机数的累积和（来自均匀分布）的时间复杂度

Question

以下循环的时间复杂度是多少？

import random  
def cummulative_sum():
   a = 0
   while a < 1:
       a += random.random()
   return a

什么保证循环会停止？毕竟，random.random() 可以一直生成 0（当然，极不可能，但仍然......）。会运行多少次？（答案取决于 random.random() 是均匀概率，但我似乎无法 link 复杂的数学）。

Answer 1

How many times will it run?

找到此循环的预期迭代次数是一个棘手的数学问题。您可以在 post 中看到一些解决方案：https://math.stackexchange.com/questions/8508/expected-number-of-0-1-distributed-continuous-random-variables-required-to-sum

显然，这甚至是 1958 年普特南测试中的一个问题（所以你知道这是一个艰难的测试）：https://prase.cz/kalva/putnam/psoln/psol583.html

What promises me that the loop will stop?

没有！ random.random() 确实可以 return 永远为 0，并且该函数永远不会终止。这在某些方面让人想起拉斯维加斯算法，因为它的预期运行时间是有限的，但它的最坏情况运行时间是无限的。

您甚至可以通过实验探索您的平均运行时间，如下所示：

import random  
import math

def cummulative_sum():
    a = 0
    iterations = 0
    while a < 1:
        a += random.random()
        iterations += 1
    return iterations

def main():
    total_iterations = 0
    runs = 1_000_000
    for _ in range(runs):
        total_iterations += cummulative_sum()

    print('Average number of iterations:', total_iterations / runs)
    print('e:                           ', math.e)

main()

只要总和小于 1，随机数的累积和（来自均匀分布）的时间复杂度

Time-complexity of cummulative sum of random numbers ( from uniform distribution ) as long as sum is less than 1

python

random

cumsum