algorithm - 这个 BFS 算法的时间复杂度是多少？

Question

我看了 LeetCode 题 270. Perfext Squares :

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.>

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

我用下面的算法解决了这个问题:

def numSquares(n):
    squares = [i**2 for i in range(1, int(n**0.5)+1)]
    step = 1
    queue = {n}
    while queue:
        tempQueue = set()
        for node in queue:
            for square in squares:
                if node-square == 0:
                    return step
                if node < square:
                    break
                tempQueue.add(node-square)
        queue = tempQueue
        step += 1

它基本上尝试通过减去每个可能的数字来从目标数字变为 0，这些数字是:[1 , 4, 9, .. sqrt(n)] 然后对每个获得的数字做同样的工作。

问题

这个算法的时间复杂度是多少？每一层的分支都是sqrt(n)次，但有些分支注定要提前结束……这让我想知道如何推导时间复杂度。

Answer 1

如果您考虑一下自己在做什么，您可以想象您正在对具有 n + 1 个节点(0 和 n 之间的所有自然数，包括 0 和 n，包括在内)和一些数量的图进行广度优先搜索边m，我们稍后会确定。您的图表本质上表示为邻接列表，因为在每个点您都遍历所有传出边(小于或等于您的数字的方 block )并在您认为方 block 太大时立即停止。因此，运行时间将为 O(n + m)，我们现在要做的就是计算出 m 是多少。

(这里还有另一个成本是计算直到并包括 n 的所有平方根，但这需要时间 O(n^1/2)，这主要由 O(n) 项决定。 )

如果您考虑一下，每个数字 k 的出边数将由小于或等于 k ​​的完全平方数给出。该值等于 ⌊√k⌋(查看几个示例 - 它有效!)。这意味着边的总数上限为

√0 + √1 + √2 + ... + √n

我们可以证明这个和是 Θ(n^3/2)。首先，我们将这个和的上限设置为 O(n^3/2)，我们可以通过注意到这一点来做到这一点

√0 + √1 + √2 + ... + √n

≤ √n + √n + √ n + ... + √n (n+1) times

= (n + 1)√n

= O(n^3/2).

要在 Ω(n^3/2) 处下限，请注意

√0 + √1 + √2 + ... + √ n

≥ √(n/2) + √(n/2 + 1) + ... + √(n) (drop the first half of the terms)

≥ √(n/2) + √(n/2) + ... + √(n/2)

= (n / 2)√(n / 2)

= Ω(n^3/2).

总的来说，边的数量是 Θ(n^3/2)，所以使用广度优先搜索的常规分析我们可以看到运行时间将是 O(n ^3/2).

这个界限可能并不严格，因为这假设您访问了每一个节点和每一个边缘，这是不会发生的。但是，我不确定如何收紧更多内容。

请注意 - 这将是使用 A* 搜索而不是广度优先搜索的好地方，因为您可以很容易地想出启发式方法来低估剩余的总距离(例如，取数字并将其除以小于它的最大完美平方)。这将导致搜索集中在非常有希望的路径上，这些路径在不太好的路径之前迅速跳向 0，例如，总是采取大小为 1 的步骤。

希望这对您有所帮助!