0
私の理解によると、DFSとBFSはどちらもO（V + E）です。しかし、検索アルゴリズムの時間複雑度が異なる可能性はありますか？Leetcode：bfs/dfsの時間複雑度
たとえば、DFSを使用するこの問題（https://leetcode.com/problems/kill-process/#/description）では、BFSよりも時間がかかります。
BFS：
class Solution(object):
def bfs(self, pid, ppid, tmp, output):
child = []
for i in xrange(len(ppid)):
if ppid[i] in tmp:
output.append(pid[i])
child.append(pid[i])
if child != []:
self.bfs(pid, ppid, child, output)
def killProcess(self, pid, ppid, kill):
"""
:type pid: List[int]
:type ppid: List[int]
:type kill: int
:rtype: List[int]
"""
output, tmp = [kill], [kill]
self.bfs(pid, ppid, tmp, output)
return output
時間計算：O（NlgN）
DFS：
class Solution(object):
def dfs(self, pid, ppid, kill, output):
for i in xrange(len(ppid)):
if ppid[i] == kill:
if kill not in output:
output.append(kill)
self.dfs(pid, ppid, pid[i], output)
if kill not in output:
output.append(kill)
def killProcess(self, pid, ppid, kill):
"""
:type pid: List[int]
:type ppid: List[int]
:type kill: int
:rtype: List[int]
"""
output = []
self.dfs(pid, ppid, kill, output)
return output
時間計算：すべてのO（N^2）
'ppid'の種類は何ですか？私はあなたが各回帰呼び出しで 'ppid'を渡しているのを見ています。それは各ノードの訪問で反復されます。これは非効率的で、DFSアルゴリズムの実装に固有のものではありません。 – Dai
@Daiありがとう！ 'ppid'はリストです。 Btw、私はもう一度同じパスに行きません。なぜなら、 'ppid'は各再帰呼び出しで何度も繰り返されます。 –
あなたのコードはDFSではありません。ツリー上のノードを訪れるのではなく（ノードの子という概念はコードにはありません）、 'ppid'リストをループしているすべての繰り返ししたがって、 'O（n^2）'ランタイムの複雑さです。 'output（）'演算子を使用すると、 'O（n）'時間に 'output'を繰り返します（私はPythonに精通していません） - ハッシュセットやハッシュマップ配列、辞書）型の代わりに 'O（1）'ルックアップを使用します。 – Dai