Leetcode: Zeit Komplexität für bfs/dfs

Nach meinem Verständnis, beide DFS und BFS nehmen O (V + E). Aber ist es möglich, dass die Suchalgorithmen unterschiedliche Zeitkomplexitäten haben?Leetcode: Zeit Komplexität für bfs/dfs

Zum Beispiel, in diesem Problem (https://leetcode.com/problems/kill-process/#/description) dauert die Verwendung von DFS länger als 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

Zeitkomplexität: 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

Zeitkomplexität: O (n^2)

Quelle

2017-05-20 Gowtham Ganesh

Was die Art der 'ppid' ist? Ich sehe, dass Sie in jedem rekursiven Aufruf, der dann bei jedem Knoten-Besuch iteriert wird, "pipid" einreichen - das ist ineffizient und in keiner Implementierung des DFS-Algorithmus inhärent. – Dai

@Dai Danke! 'ppid' ist eine Liste. Übrigens, da ich den gleichen Pfad nicht nochmal durchführe (obwohl "ppid" bei jedem rekursiven Aufruf immer wieder durchlaufen wird), ist das nicht immer noch DFS? –

Ihr Code ist nicht DFS, weil Sie über eine Liste iterieren, Knoten in einem Baum nicht besuchen (Ihr Code hat kein Konzept für die Knoten eines Knotens), und bei jeder Iteration durchlaufen Sie die 'pid'-Liste daher die 'O (n^2) 'Laufzeitkomplexität. Ihre Verwendung des 'in output'-Operators wird auch über 'output' in' O (n) 'time iterieren (ich glaube - ich bin nicht allzu versiert in Python) - Sie sollten ein hashset oder hashmap (assoziative- Array, Dictionary) für 'O (1) 'Lookup statt. – Dai

Zu allererst Die Komplexität von Algorithmen hängt von den verwendeten Datenstrukturen ab. Die Komplexität von BFS und DFS ist nur dann O (V + E), wenn Sie die Adjazenzlisten-Darstellung des Graphen verwenden.

Zweitens verwaltet der Code keine besuchte Gruppe von Knoten, die auf Backtrack verwiesen wird, und nicht die gleichen Knoten erneut zu besuchen.

Daraus ergibt sich die Komplexität des Codes ist O (n^2) und nicht O (V + E)

Quelle

2017-05-21 00:45:29

Leetcode: Zeit Komplexität für bfs/dfs

Antwort

Verwandte Themen