Vielen Dank an alle, die mit Ideen und alternativen Lösungen geantwortet haben. Effizientere Wege zur Lösung von Problemen sind immer willkommen, sowie Erinnerungen, um meine Annahmen in Frage zu stellen. Trotzdem möchte ich Sie bitten, für einen Moment zu ignorieren, welches Problem ich mit dem Algorithmus lösen möchte, und mir dabei zu helfen, die Komplexität meines Algorithmus zu analysieren, wie ich ihn geschrieben habe - ein ganz einfacher Weg in einem Diagramm mit tiefenbegrenzter Suche wie beschriebenHierund implementiertHier. Vielen Dank!

Bearbeiten: Dies sind Hausaufgaben, aber ich habe diese Aufgabe bereits eingereicht und möchte nur wissen, ob meine Antwort korrekt ist. Ich bin etwas verwirrt über die Komplexität von Big-O, wenn es um Rekursion geht.

Ursprüngliche Frage unten:

Ich versuche, die Komplexität einer Suche mit allen Pfaden zu finden, wie sie von gegeben istdiese Algorithmus. Bei zwei gegebenen Eckpunkten finde ich alle einfachen Pfade zwischen ihnen mithilfe einer Tiefensuche.

Ich weiß, dass die zeitliche Komplexität von DFS O (V + E) und die räumliche Komplexität O (V) ist, und meine Intuition ist, dass die Komplexität einer Suche mit allen Pfaden größer sein wird, aber ich kann nicht Bestimmen Sie, was es sein wird.

Verwandte SO-FragenHier undHier.

Update (als Antwort auf einen Kommentar unten):

Ich versuche das zu lösensechs Grad von Kevin Bacon Problem. Dies erfordert im Allgemeinen das Finden des niedrigsten Trennungsgrades zwischen einem Paar von Akteuren, aber ich muss ALLE Trennungsgrade finden (vorerst weniger als 6, aber das kann sich ändern).