时间戳

首页 > 解决方案 > 迭代不可预测的 while 循环的时间复杂度是多少？

python - 迭代不可预测的 while 循环的时间复杂度是多少？

问题描述

我写了这个算法，其中while循环可以根据输入数组从N变化到0，但我们也不能给出O（N * N），因为如果while循环执行一次N次，那么对于下一次迭代x 它将为 0，因为我们正在从字典中删除它，结果循环将在第一次迭代中中断。那么这个算法在最坏情况下的时间复杂度是多少。如果您需要了解算法，这就是问题所在。[https://www.youtube.com/watch?v=XitBQzqC1O0]

x=[5,4,4,3,3,2]
destroyedBaloons={}
count=0
for i in x:
    if(destroyedBaloons.get(i)):
        destroyedBaloons[i]+=1
    else:
        destroyedBaloons[i]=1
for i in x:
    if(not(destroyedBaloons.get(i))):
        continue
    height =i
    while(height>0):
        if(destroyedBaloons.get(height)):
            destroyedBaloons[height]-=1
            height-=1
        else:
            break
    count+=1    
print(count)```

标签： pythontime-complexityspace-complexityballoon

解决方案

最糟糕的情况是气球按非递减顺序排列，因此每个气球都需要一个箭头。第一个循环将是N次迭代，然后是N - 1、N - 2等，因此总迭代次数将是½(N² + N)或O(N²)。

推荐阅读