时间复杂度

来源：9-3 发现重叠子问题 Integer Break

tobeabee

2022-08-16

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

写回答

1回答

liuyubobobo

2022-08-17

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

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

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

继续加油！：）

tobeabee

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

2022-08-17

共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 2