Leetcode上加热器问题解决方案的时间复杂性

Question

从Leetcode上的一个流行问题考虑此python解决方案：

 def findOptimalRadius(houses, heaters):
        houses.sort()
        heaters.sort()
        last = len(heaters) - 1
        x1,x2 = 0,0
        res = 0
        for house in houses:
            while x2 < last and house > heaters[x2]:
                x1, x2 = x2, x2+1
            dist1,dist2 = abs(heaters[x1] - house), abs(heaters[x2] - house)
            res = max(res, min(dist1,dist2))
        return res

（给定N个房屋和M个加热器）

显然，如果我们在开始时对两个数组进行排序，那么空间复杂度被认为是O（N logn+M logm），如果它们已经排序，那么空间复杂度被认为是O（N+M）

但是我不明白为什么for循环和嵌套while循环只解释O（N+M）

它不应该是O（N*M），因为它们是嵌套的，在最坏的情况下，while循环将遍历所有加热器

感谢您帮助我理解如何计算这种情况下的时间复杂度

Answer 1

它是O（N+M），因为第二个循环对于每个元素只运行一次。如果您注意到，x2从不减少，它总是从最后一个状态继续，并增加1，因此当它达到值时，最后一个循环永远结束。所以，它不是每次都通过阵列加热器中的每个元件，而是只通过一次，当到达其末端时，即使阵列房屋中仍然有元件，但循环不会启动

至于你的直觉。如果阵列房屋中的每个元素都要穿过每个加热器，这是正确的，但事实并非如此

请注意，具有嵌套循环并不自动意味着时间复杂度为O（N*M）（在本例中）或O（N^x）（x是嵌套循环的数量）。您必须分析每个单独的循环在做什么

编辑： 注释说明如下：

N=20
M=15

i= current for loop element 
j= current while loop element

i=1 -> j = 1 , 2 , 3 , 4
i=2 -> j = 4 , 5
i=3 -> j = 5 , 6 , 7 , 8 
i=4 -> j = 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15
i=5 -> j = 15 (while loop is at its end so it won't be initiated)
i=6 -> j = 15 
 .
 .
 .
i=20 -> j = 15 

您可以注意到，当while循环到达阵列加热器的末端时，它将结束并且不再启动。因此while循环的复杂性为O（M），for循环的复杂性为O（N）。由于while循环不是针对每个i重新启动，而是从最后一个状态开始继续，因此总的复杂性是O（N+M），而不是O（N*M）

试想一下这样一个事实，即你只通过加热器中的每个元素一次，对房屋也是如此（你永远不会再访问某些元素）

如果你重新审视每栋房子的整个加热器阵列，那么复杂性确实是O（N*M）