非终止型算法的Big O分析：5位唯一学生ID生成算法复杂度求解

最坏情况复杂度 #

这个算法没有确定的终止保证——因为它不记录之前生成过的失败ID，理论上可能无限次重复生成已存在的ID，导致循环永远无法退出。因此最坏时间复杂度为O(∞)，不存在明确的时间上界。

平均情况复杂度 #

这属于「随机抽样直至命中未占用值」的场景，我们通过期望尝试次数来拆解分析：
假设当前数据库中已存储k个唯一ID，剩余可用ID数量为N - k（此处N=100000）。每次随机生成ID时，命中可用ID的概率为p = (N - k)/N。

根据几何分布的特性，成功抽取到可用ID前的期望尝试次数为1/p = N/(N - k)。而每次尝试包含的两个核心操作：

• 生成随机5位ID：固定长度的随机数生成，属于O(1)操作；
• 检查ID是否存在于数据库：若数据库采用哈希索引等高效查询结构，该操作也为O(1)。

因此平均时间复杂度为O(N/(N - k))：

• 当数据库中已用ID极少（k << N）时，复杂度趋近于O(1)，多数情况下一次生成即可命中；
• 当ID池接近耗尽（k趋近于N）时，复杂度会急剧上升至O(N)——例如仅剩1个可用ID时，平均需要100000次尝试才能命中目标。

算法缺陷说明 #

该算法的设计存在明显问题：不仅可能陷入无限循环，且在ID池剩余量不足时效率会断崖式下跌。更优的实现方案包括维护可用ID集合、采用递增生成策略等，可从根源避免无效的重复尝试。

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