计算图中路径的递归函数的复杂性

Question

我找到了一个用于有向图的函数，对于其中的顶点“u”和“v”，它会计算从“u”到“v”的所有可能路径，并且路径上恰好有 k 个边。代码和算法来自here。所以，

// C++ program to count walks from u to v with exactly k edges
#include <iostream>
using namespace std;

// Number of vertices in the graph
#define V 4

// A naive recursive function to count walks from u to v with k edges
int countwalks(int graph[][V], int u, int v, int k)
{
   // Base cases
   if (k == 0 && u == v)      return 1;
   if (k == 1 && graph[u][v]) return 1;
   if (k <= 0)                return 0;

   // Initialize result
   int count = 0;

   // Go to all adjacents of u and recur
   for (int i = 0; i < V; i++)
       if (graph[u][i])  // Check if is adjacent of u
           count += countwalks(graph, i, v, k-1);

   return count;
}

我试图找到并证明这个算法的复杂性。根据 post:

"The worst case time complexity of the above function is O(V^k) where V is the number of vertices in the given graph. We can simply analyze the time complexity by drawing recursion tree. The worst occurs for a complete graph. In worst case, every internal node of recursion tree would have exactly n children."

但是，我找不到导致我可以分析以证明该算法是 O(V^k) 的树的递归。另外，我认为最好的情况是 Theta(1)。真的吗？平均情况如何？

Answer 1

对于完整的图，每个节点都相互连接，因此您的 for 循环将进行 |V| 递归调用。这将在每次递归调用时发生，直到 k 变为 1，因此总共 O(|V|^k) 次递归调用。

你可以这样表达：

T(V, k) = |V|*T(V, k - 1)
        = |V|*|V|*T(V, k - 2)
        = |V|^2*|V|*T(V, k - 3)
        = ...

总是T(V, _)因为一个节点可以被多次访问

最好的情况确实是 O(1)，即在第一次调用期间触发前三个 if 条件之一。

平均情况我不确定，但我认为应该还是很糟糕。考虑一个链表图和一个巨大的 k：为了使 k 变为 0 或 1，您将多次遍历相同的边。随着路径的增加，情况会变得越来越糟。

Answer 2

一般 "average case" 分析在像这样的问题中有点不适，因为您可以选择如何定义 "random" 图。一种方法是说对于 0 <= p <= 1，每个可能的边都以某种概率 p 出现，然后尝试根据 p 分析平均情况运行时间。但是还有其他方法可以定义随机图。平均案例分析通常也很困难。但是，如果你用 "average" 定义你的意思（即随机图是什么意思）那么有人可能会尝试一下。

计算图中路径的递归函数的复杂性

Complexity of a recursive function that counts paths in graph

c++

algorithm

recursion

graph

time-complexity