服从均匀分布的随机数累加至超过1的循环时间复杂度是多少

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

1. 时间复杂度 #

• 平均时间复杂度为O(1)：该函数无输入参数，循环运行次数的期望是固定常数，和任何输入规模无关，因此平均复杂度是常数阶。
• 最坏时间复杂度无明确上界：理论上存在连续多次返回极小值的可能，最坏情况下运行次数可以无限大，但该场景发生的概率趋近于0。

2. 循环终止的保证 #

理论上确实存在random.random()持续输出0导致循环永不终止的可能，但该场景属于零概率事件，在算法分析的常规语境下默认零概率事件不会发生。
另外实际工程实现中，random.random()返回的是有限精度的浮点数，不存在无限接近0的返回值，因此实际运行时循环必然会终止。

3. 循环期望运行次数 #

这个是概率论中的经典问题：求最小的正整数n，使得n个独立的(0,1)区间均匀分布随机变量的和大于1，n的期望为自然常数e（约等于2.718）。也就是说平均运行不到3次循环就会退出。

内容的提问来源于stack exchange，提问作者jacob12