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

Question

我看了LeetCode上的问题270. 完全平方数：

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

问题

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

该算法基本上通过减去每个可能的数字来从目标数到0，这些数字包括：[1、4、9、sqrt(n) 等]，然后对获取的每个数字执行同样的操作。

- cs guy

Answer 1

如果你思考一下你正在做的事情，你可以想象自己在一张有 n + 1 个节点（包括 0 到 n 之间所有自然数）和某些边 m 的图上进行广度优先搜索，我们稍后会确定 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之前，而不是像每次只走一步那样，搜索较差的路径。

希望这可以帮助到您！

- templatetypedef

Answer 2

一些观察结果：

1. 小于 n 的平方数的数量为 √n（向下取整）
2. while 循环第一次迭代后，tempQueue 将有 √n 个条目
3. tempQueue 不可能有超过 n 个条目，因为所有这些值都是正数，小于 n 并且唯一。
4. 每个自然数都可以写成四个整数平方的和。这意味着您的 BFS 算法的 while 循环最多会迭代 4 次。如果在前三次迭代中没有执行 return 语句，则保证第 4 次迭代将执行。
5. 除了 squares 的初始化语句外，每个语句都在常量时间内运行，即使是对 .add() 的调用也是如此。
6. squares 的初始化具有列表推导式循环，它有 √n 次迭代，并且 range 在常量时间内运行，因此该初始化的时间复杂度为 O(√n)。

现在我们可以将 if node-square == 0 语句在最内层循环体中执行的次数设定为上限：

        1⋅√n + √n⋅√n + n⋅√n + n⋅√n

每个乘积的左因子对应于特定迭代中 queue 的最大大小，右边的因子对应于 squares 的大小（始终相同）。 这简化为：

        √n + n + 2n^3⁄2

按时间复杂度计算，这是：

        O(n^3⁄2)

这是最坏情况下的时间复杂度。当 while 循环只需要迭代两次时，它是 O(n)，而当只有一次（当 n 是平方数时），则是 O(√n)。

- trincot