搜索类题目（DFS/BFS）时间复杂度的分析

1、 想问一下大家，对于有些DFS和BFS解法的题目，时间复杂度比较难解，大家平时是怎么准备、分析的呢？  看LC上有些题目的disscuss里，有的帖子没有人分析时间复杂度，或者有的帖子里对于时间复杂有争议，没有统一的答案。
2、 然后就是这类问题的面试的时候应该要怎么和面试官交流呢？是需要一步一步写公式推导or直接给答案然后大概分析一下？

3、有些公司比如FB是一定会要求分析复杂度的，遇到搜索类问题应该怎么回答呢？还是说一般面试官给搜索类题目的话就不会问了？


谢谢大家指教！

你很笼统的说这些叫bfs 、 dfs是没错的， 因为graph traversal 确实也就这么两种分类。

这两个有一个共同点就是 bfs 和 dfs 一定是 O(N) time， 是每个node 都只走一遍的。

如果有不一样的话那就是带了其他算法， 经典的比如迪杰克斯拉， 比如prim， 比如kruskal， 会对着edge排序。 那么这样做就是 O(nlge）， e是edges的数目。 如果图一定是紧密的话， 那么edge的数量会很大， 接近n方。

[133] bfs | dfs 都可以， 简单的走一遍。 O[n]

[286] bfs, 因为你想找最近的点。 每个0点都可以走一遍bfs ，所以最坏情况是 O[mn * mn]。。 吗？

[127] bfs, 也是找最近的走法， 所以bfs。 这个最长判断次数是每个字母位置上都改26次。 所以26 * n

[210] bfs. 这个是拓扑sort， kahn's algorithm, 一共n个点走完完事。 O[n]

[785] dfs | bfs. 每个点走一遍 O[n]。

这些题都不涉及edge的长度或者weight， 所以基本都是number of nodes

补充内容 (2018-8-7 12:40):
[286] 最坏情况应该是类似O[kmn] 因为有dp告诉我每一个点visit的时候就知道他最好的情况在哪里，mn是必须得走一遍的。 k是0的个数。

一步一步推恐怕不合适吧. 应该可以直接报答案不是么.?

除非是有些地方你想错了或者什么.

你有具体例子没.

肥宅快乐水 发表于 2018-8-6 23:54
一步一步推恐怕不合适吧. 应该可以直接报答案不是么.?

除非是有些地方你想错了或者什么.

谢谢回答！

比如最近做的几道题：
133 Clone Graph
286 Walls and Gates
127 Word Ladder
120 Course Schedule II
785 Is Graph Bipartite?
做完自己想了一下复杂度，感觉都模模糊糊的.... 看discuss的帖子也没能找到很确定的答案。

[286] 最坏情况应该是类似O[kmn]

这个怎么讲？就是O(m*n)吧

Here is a video from youtube , really helps me a log . https://www.youtube.com/watch?v= ... beHBDD42pqqG36jhuOr

肥宅快乐水 发表于 2018-8-7 12:38
你很笼统的说这些叫bfs 、 dfs是没错的， 因为graph traversal 确实也就这么两种分类。

这两个有一个共 ...

想请教一下为什么都是O(N)的啊，比如要是一个完全图求BFS，对每个节点都要遍历与其相邻接的N-1个节点，那不是O(N^2)了吗