在 Leetcode 上解决加热器问题的时间复杂度

Question

考虑这个 python 来自 Leetcode 上一个热门问题的解决方案：

 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 个加热器）

显然，如果我们在开始时对两个数组进行排序，space 复杂度被认为是 O(N log N + M log M)，如果它们已经排序则为 O(N+M)。

但是我不明白为什么for循环和嵌套的while循环只占O(N+M)。

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

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

Answer 1

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

至于你的直觉。如果对于阵列房屋中的每个元素，您将遍历每个加热器，这将是正确的，但事实并非如此。

请注意，具有嵌套循环并不自动意味着时间复杂度为 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)。

在 Leetcode 上解决加热器问题的时间复杂度

Time complexity for a solution to the heater problem on Leetcode

python

big-o

time-complexity

while-loop