对于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.
它所做的基本上是试图通过减去每个可能的数字从目标数变为0，这些数字是：[1，4，9sqrt（n）]，然后对获得的每个数字执行相同的工作。我很难理解这个算法的时间复杂度，因为每个级别的分支都是Sqt（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
最佳答案
如果你想想你在做什么，你可以想象你在一个有n+1个节点（所有自然数在0和n之间，包括0和n）和一些边m的图上做广度优先搜索，我们稍后会确定你的图本质上被表示为一个邻接列表，因为在每一点上你都迭代所有的输出边（小于或等于你的数字的正方形），一旦你认为一个太大的正方形就停止因此，运行时将是O（n+m），我们现在要做的就是找出m是什么。
（在计算n之前（包括n）的所有平方根时还有另一个成本，但这需要时间O（n1/2），O（n）项占主导地位。）
如果你仔细想想，每个数字k的输出边的数量将由小于或等于k的完美正方形的数量给出。该值等于⌊√k⌋（请检查几个示例-它有效！）。这意味着边的总数上限为
0+√1+√2+…+√无
我们可以证明这个和是（n3/2）。首先，我们将这个和的上界设为O（n3/2），注意
0+√1+√2++√无
≤√n+√n+√n++√n（n+1）次
=（n+1）√n
=O（N3/2）。
要在Ω（n3/2）处下限，请注意
0+√1+√2+…+√无
不小于√（n/2）+√（n/2+1）++√（n）*（去掉前半部分）
不小于√（n/2）+√（n/2）+…+√（N/2）
=（n/2）√（n/2）
=Ω（n3/2）。
因此，总的来说，边的数量是Θ（n3/2），所以使用广度优先搜索的常规分析，我们可以看到运行时将是O（n3/2）。
这个界限可能不紧，因为这假设您访问每个节点和每个边缘，这是不会发生的。然而，我不知道如何收紧事情远超过这一点。
值得注意的是，这将是一个使用*搜索而不是广度优先搜索的好地方，因为您可以很容易地想出启发式方法来低估剩余的总距离（比如，取这个数字并除以小于它的最大完美平方）。这将导致搜索的重点放在极有希望的路径上，这些路径在不太好的路径（比如说，总是采取大小为1的步骤）之前快速地跳向0。
希望这有帮助！
关于algorithm - 这个BFS算法的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56776263/