包括随机性在内的复杂性

Question

我有以下三个循环：

for i in range(m)
    for j in range(n)
        r = random(0,l)
        for k in range(r)
            
        l = l-r

我想知道这里的复杂性是什么，最后一个是否等于

O(1)

？前两个循环应该是

O(m*n)

。

l,m,n

当然是整数。

Answer 1

𝑙的原始值将最大值设置为内循环可以进行迭代的total次数。换句话说，𝑟将得到的所有值的总和不能超过𝑙的原始值。

因此，对于外部两个循环，我们有 θ(𝑛𝑚)，并添加内部循环迭代总数的最坏情况，我们得到 O(𝑛𝑚+𝑙) 的最坏情况时间复杂度。

注意：当 random 始终返回 0 时，就会出现

best

情况。在这种情况下，我们得到 θ(𝑛𝑚) 作为时间复杂度。