Graph DFS 复杂度到底是多少哦

今年面试遇到一个flood fill的变种，我就用标准graph dfs做了，访问过的结点也mark了visited。
但最后面试官说这其实是exponential的复杂度，我就？？？以前上课学的graph dfs不就是O(m+n)吗？如果真的是指数复杂度怎么还编进教材里？
还是我孤陋寡闻？求解

贴代码，不贴代码怎么看

讲道理应该每个node都是visit一次吧 m*n吧。不知道具体是什么题目。

面试官 != 真理，而且应该是O(M*N)吧

说O(M*N)的是怎么算出来的啊🤦‍♂️

如果大概是flood fill那种题目的话 M/N是长和宽 那肯定是O(M*N)

就想想最差的Case，每一个点都要标记，那不就是M*N

面试官不一定说的就是对的 但时间复杂度这种东西也不能死记硬背书上 肯定看不同题目具体分析

tiancaihb 发表于 2022-3-25 15:24
说O(M*N)的是怎么算出来的啊🤦‍♂️

可能说的是二维矩阵吧，m,n是长和宽，点的总数是m*n

我事后还跑了case，count tick，就拿他举的counter example，就是线性的，这能和recruiter argue吗？面试官应该也要把code递交上去的吧
面试的时候都没几分钟了，没时间思考和反驳

idealmaster 发表于 2022-3-25 15:41
可能说的是二维矩阵吧，m,n是长和宽，点的总数是m*n

如果说用临接矩阵存的图，那么n*n（n是点数）还可以理解🤔 矩阵倒是也说得通m*n吧……