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

Question

对于问题https://leetcode.com/problems/perfect-squares/我已经使用以下算法解决了它。问题是

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

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

它所做的基本上是尝试通过减去每个可能的数字（[1, 4, 9, .. sqrt(n)] 来从目标数字变为 0，然后对获得的每个数字进行相同的工作。我很难理解这个算法的时间复杂度，因为每个级别的分支都是 sqrt(n) 次，但有些分支注定要提前结束......

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

Answer 1

如果您考虑一下您在做什么，您可以想象您正在对具有 n + 1 个节点（0 和 n 之间的所有自然数，包括 0 和 n 之间的所有自然数）和一些边数 m 的图进行广度优先搜索，我们将在稍后确定。您的图形基本上表示为一个邻接列表，因为在每个点上，您都会遍历所有传出边（小于或等于您的数字的平方），并在您认为正方形太大时立即停止。结果，运行时间将是 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) 次

= (n + 1)?n

= O(n ^3/2 )。

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

?0 + ?1 + ?2 + ... + ? n

? ?(n/2) + ?(n/2 + 1) + ... + ?(n) （去掉前半项）

? ?(n/2) + ?(n/2) + ... + ?(n/2)

= (n / 2)?(n / 2)

= ?(n ^3/2 )。

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

这个界限可能并不严格，因为这假设您访问每个节点和每个边缘，这不会发生。但是，我不知道如何收紧更多的东西。

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

希望这可以帮助！