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

Question

我编写了这个算法，其中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)```

Answer 1

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