如何计算随机数生成算法的时间复杂度及预估运行时长

算法说明 #

该算法实现了一个随机数列表生成函数randomRegisteredVisits，接收参数size后，通过循环调用randrange(0, size)生成随机数并添加到列表，直到列表长度等于size，最终返回该列表。

测试数据 #

已针对不同输入规模测试运行时长，结果如下：

时间复杂度分析 #

从代码逻辑来看，循环会恰好执行size次：每次循环向列表添加一个元素，从空列表开始直到长度达标。而每次循环内的randrange调用和列表append操作都是常数时间复杂度O(1)，因此整个算法的时间复杂度为O(n)（n即输入参数size），这也和测试数据呈现的线性增长趋势一致——输入规模扩大10倍时，运行时长也近似扩大10倍。

运行时长预估的数学方法 #

要预估任意size对应的运行时长，可通过测试数据拟合线性模型实现：

1. 假设运行时长T(n)与输入规模n满足线性关系：T(n) = k * n + c，其中k是单个元素生成的耗时系数，c是函数调用、列表初始化等固定开销。
2. 利用已有测试数据计算参数：
   • 当n较大时，固定开销c的占比极低，可忽略不计。通过大样本数据近似计算k：
     • n=10000时，k≈0.007082/10000=7.082e-7 秒/个
     • n=100000时，k≈0.068690/100000=6.869e-7 秒/个
   • 取k的平均值约6.9755e-7 秒/个，那么n=1000000时，预估时长≈6.9755e-7 * 1000000 ≈ 0.698秒。
3. 若需要更精确结果，可用最小二乘法对所有测试数据进行线性拟合，得到更准确的k和c值后代入计算。

算法代码 #

from random import randrange
from datetime import datetime

def randomRegisteredVisits(size):
    randomNumbersList = []
    while (len(randomNumbersList) != size):
        randomNumbersList.append(randrange(0, size))
    return randomNumbersList

start_time = datetime.now()
miTestofRandom = randomRegisteredVisits(1000000)
end_time = datetime.now()
print('Duration: {}'.format(end_time - start_time))

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