Lea*_*ner 18 algorithm time-complexity depth-first-search
我开始学习时间复杂性,我在实例中查看了一些简单的时间复杂度.
我想知道我们如何计算平均时间复杂度为一个图表,深度优先搜索|V|=n和|E|=m,让起始节点是"U"和终端节点是"V".
gab*_*ish 25
DFS的时间复杂度为O(n + m).考虑到我们只访问每个节点一次这样的事实,我们得到了这种复杂性,而在树的情况下(没有周期),我们正在越过所有边缘一次.
例如,如果起始节点是u,并且结束节点是v,我们正在考虑最坏情况下v将是最后访问的节点.所以我们开始访问每个第一个邻居的u连接组件,然后是第二个邻居的连接组件,依此类推,直到最后一个邻居的连接组件,我们在那里找到v.我们只访问了每个节点一次,并没有越过同一个边缘不止一次.