时间复杂度

Question

老师，对于279完全平方数问题，我发现动态规划的时间效率还没有以前用图的效率高，用图的时间复杂度是多高呢

Answer 1

liuyubobobo 2022-08-17 01:19:12

BFS 的时间复杂度是 O(V + E)，其中 V 是图中的节点数，E 是边数。

在这个问题中。节点数就是 n。边数的上界是：对于每一个数字 n，<= n 的完全平方数有 sqrt(n) 个，所以每个数字最多有 sqrt(n) 条边，总体总共有 n * sqrt(n) 条边。

所以整体时间复杂度是 O(n + nsqrt(n)) = O(nsqrt(n))。

继续加油！：）

• 提问者 tobeabee #1

  那这个复杂度跟动态规划的复杂度其实是一样的，我觉得区别可能在于动态规划需要把n及其前面的每个数的情况都算出来，但用图就不需要，因为一旦找到最短距离就可以提前结束队列操作，而不必真的去访问所有n个结点