这个 BFS 算法的时间复杂度是多少？
What is the time complexity of this BFS algorithm?
我看了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)次，但有些分支注定要提前结束……这让我想知道如何推导时间复杂度。
如果您仔细想想自己在做什么，您可以想象您正在对具有 n + 1 个节点（0 到 n 之间的所有自然数，包括 0 和 n）的图形进行 breadth-first 搜索和一些边数 m，我们将在稍后确定。您的图表本质上表示为邻接列表，因为在每个点您都遍历所有传出边（小于或等于您的数字的方块）并在您认为方块太大时立即停止。结果，运行时间将是 O(n + m)，我们现在要做的就是计算出 m 是多少。
（这里还有一个成本是计算所有平方根直到并包括 n，但这需要时间 O(n1/2)，这是由 O (n) 项。)
如果你考虑一下，每个数k的出边数将由小于或等于k的完全平方数给出。该值等于 ⌊√k⌋（查看几个示例 - 它有效！）。这意味着边的总数是 upper-bounded by
√0 + √1 + √2 + ... + √n
我们可以证明这个和是 Θ(n3/2)。首先，我们将 upper-bound 这个和 O(n3/2)，我们可以通过注意到
√0 + √1 + √2 + ... + √n
≤ √n + √n + √ n + ... + √n (n+1) times
= (n + 1)√n
= O(n3/2).
到lower-bound这个在Ω(n3/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)
= Ω(n3/2).
所以总的来说，边的数量是 Θ(n3/2)，所以使用 breadth-first 搜索的常规分析我们可以看到运行时将是 O(n3/2).
这个界限可能并不严格，因为这假设您访问了每一个节点和每一个边缘，这是不会发生的。但是，我不确定如何收紧更多东西。
请注意 - 这将是一个 很棒 使用 A* 搜索而不是 breadth-first 搜索的地方，因为您可以很容易地想出启发式方法来低估剩余的总距离（例如，取数字并将其除以小于它的最大完美平方）。这将导致搜索集中在非常有前途的路径上，这些路径在 less-good 路径之前迅速跳向 0，比如，总是采取大小为 1 的步骤。
希望对您有所帮助！
一些观察：
- 到n的方格数是√n（取整数）
- 在
while 循环的第一次迭代后，tempQueue 将有 √n 个条目
tempQueue 永远不会超过 n 个条目，因为所有这些值都是正数，小于 n 并且是唯一的.- 任何自然数都可以写成
。所以这意味着你的 BFS 算法的 while 循环将最多迭代 4 次。如果 return 语句在前 3 次迭代中的任何一次都没有执行，则保证它会在第 4th.
- 每个语句（除了
squares 的初始化）都在恒定时间内运行，甚至是对 .add(). 的调用
-
squares 的初始化有一个列表理解循环，有 √n 次迭代，并且 range 在恒定时间内运行，因此初始化有一个O(√n). 的时间复杂度
现在我们可以为 if node-square == 0 语句（或最内层循环体中的任何其他语句）的执行次数设置上限：
1⋅√n + √n⋅√n + n⋅√n + n⋅√n
4 项中的每一项都对应于 while 循环的一次迭代。每个产品的左侧因子对应于该特定迭代中 queue 的最大尺寸，右侧的因子对应于 squares 的尺寸（始终相同）。这简化为：
√n + n + 2n3⁄2
就时间复杂度而言，这是：
O(n3⁄2)
这是最坏情况下的时间复杂度。当while循环只需要迭代两次时，就是O(n)，而当只需要一次（当n是一个平方），则为O(√n).
我看了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)次，但有些分支注定要提前结束……这让我想知道如何推导时间复杂度。
如果您仔细想想自己在做什么，您可以想象您正在对具有 n + 1 个节点（0 到 n 之间的所有自然数，包括 0 和 n）的图形进行 breadth-first 搜索和一些边数 m，我们将在稍后确定。您的图表本质上表示为邻接列表，因为在每个点您都遍历所有传出边（小于或等于您的数字的方块）并在您认为方块太大时立即停止。结果，运行时间将是 O(n + m)，我们现在要做的就是计算出 m 是多少。
（这里还有一个成本是计算所有平方根直到并包括 n，但这需要时间 O(n1/2)，这是由 O (n) 项。)
如果你考虑一下，每个数k的出边数将由小于或等于k的完全平方数给出。该值等于 ⌊√k⌋（查看几个示例 - 它有效！）。这意味着边的总数是 upper-bounded by
√0 + √1 + √2 + ... + √n
我们可以证明这个和是 Θ(n3/2)。首先，我们将 upper-bound 这个和 O(n3/2)，我们可以通过注意到
√0 + √1 + √2 + ... + √n
≤ √n + √n + √ n + ... + √n (n+1) times
= (n + 1)√n
= O(n3/2).
到lower-bound这个在Ω(n3/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)
= Ω(n3/2).
所以总的来说，边的数量是 Θ(n3/2)，所以使用 breadth-first 搜索的常规分析我们可以看到运行时将是 O(n3/2).
这个界限可能并不严格，因为这假设您访问了每一个节点和每一个边缘，这是不会发生的。但是，我不确定如何收紧更多东西。
请注意 - 这将是一个 很棒 使用 A* 搜索而不是 breadth-first 搜索的地方，因为您可以很容易地想出启发式方法来低估剩余的总距离（例如，取数字并将其除以小于它的最大完美平方）。这将导致搜索集中在非常有前途的路径上，这些路径在 less-good 路径之前迅速跳向 0，比如，总是采取大小为 1 的步骤。
希望对您有所帮助！
一些观察：
- 到n的方格数是√n（取整数）
- 在
while循环的第一次迭代后，tempQueue将有 √n 个条目 tempQueue永远不会超过 n 个条目，因为所有这些值都是正数，小于 n 并且是唯一的.- 任何自然数都可以写成
while循环将最多迭代 4 次。如果return语句在前 3 次迭代中的任何一次都没有执行，则保证它会在第 4th. - 每个语句（除了
squares的初始化）都在恒定时间内运行，甚至是对.add(). 的调用
-
squares的初始化有一个列表理解循环，有 √n 次迭代，并且range在恒定时间内运行，因此初始化有一个O(√n). 的时间复杂度
现在我们可以为 if node-square == 0 语句（或最内层循环体中的任何其他语句）的执行次数设置上限：
1⋅√n + √n⋅√n + n⋅√n + n⋅√n
4 项中的每一项都对应于 while 循环的一次迭代。每个产品的左侧因子对应于该特定迭代中 queue 的最大尺寸，右侧的因子对应于 squares 的尺寸（始终相同）。这简化为：
√n + n + 2n3⁄2
就时间复杂度而言，这是：
O(n3⁄2)
这是最坏情况下的时间复杂度。当while循环只需要迭代两次时，就是O(n)，而当只需要一次（当n是一个平方），则为O(√n).