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

Question

我为有向图找到了一个函数，对于其中的顶点"u"one_answers"v"，它计算从"u"到"v"的所有可能的走步，走步上正好有k条边。代码和算法来自这里。所以，

// 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;
}

我正在努力寻找并证明这个算法的复杂性。根据帖子：

"上述函数的最坏情况时间复杂度是O（V^k），其中V是给定图中的顶点数。我们可以简单地分析通过绘制递归树来计算时间复杂度。最糟糕的情况发生在完整的图形。在最坏的情况下，递归树的每个内部节点会有n个孩子。"

但是，我找不到导致树的递归，我可以分析它来证明这个算法是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, _)，因为一个节点可以被访问多次。

当前三个if条件中的一个在第一次调用期间触发时，最好的情况实际上是O(1)。

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

Answer 2

在这样的问题中，通用的"平均情况"分析有点不适定，因为您可以选择如何定义"随机"图。一种方法是说，对于0<=p<=1，然后尝试用p来分析平均案例运行时间。但也有其他方法可以定义随机图。此外，一般的案例分析往往很难。然而，如果你定义了"平均"的含义（即随机图的含义），那么有人可能会尝试一下