如何计算以下函数的时间复杂度？

Question

这是一个递归函数。它遍历字符串映射（multimap<string, string> graph）。如果 s_tmp 等于所需的字符串 (Exp)，则检查 itr -> second (s_tmp)，打印它 (itr -> first) 并执行函数又是itr -> first。

string findOriginalExp(string Exp){
    cout<<"*****findOriginalExp Function*****"<<endl;
    string str;
    if(graph.empty()){
        str ="map is empty";
    }else{
        for(auto itr=graph.begin();itr!=graph.end();itr++){
        string s_tmp = itr->second;
        string f_tmp = itr->first;
        string nll = "null";
        //s_tmp.compare(Exp) == 0
        if(s_tmp == Exp){
            if(f_tmp.compare(nll) == 0){
            cout<< Exp <<" :is original experience.";
            return Exp;
            }else{
                return findOriginalExp(itr->first);

            }
        }else{
            str="No element is equal to Exp.";
        }
     }

    }
    return str;
    }

停止没有规则，似乎完全是随机的。这个函数的时间复杂度是怎么计算的？

Answer 1

您应该使用递归关系来近似递归调用的控制流。我上大学类离散数学已经 30 年了，但通常你喜欢伪代码，只要看看有多少调用就够了。在某些情况下，只计算右侧最长条件下有多少是有用的，但您通常需要重新插入一个展开式，然后从中推导出多项式或幂关系。

Answer 2

我不打算分析你的功能，而是尝试以更一般的方式回答。看起来您正在寻找一个简单的表达式，例如 O(n) 或 O(n^2) 来表示您函数的复杂性。然而，复杂性并不总是那么容易估计。

在您的情况下，这在很大程度上取决于 graph 的内容以及用户作为参数传递的内容。

作为类比，考虑这个函数：

int foo(int x){
    if (x == 0) return x;
    if (x == 42) return foo(42);        
    if (x > 0) return foo(x-1);            
    return foo(x/2);
}

在最坏的情况下，它永远不会 return 发送给调用者。如果我们忽略 x >= 42，那么最坏情况下的复杂度是 O(n)。仅此一项对于用户来说并不是很有用的信息。作为用户，我真正需要知道的是：

永远不要用 x >= 42 来调用它。
O(1) 如果 x==0
O(x) 如果 x>0
O(ln(x)) 如果 x < 0

现在尝试对您的功能进行类似的考虑。最简单的情况是 Exp 不在 graph 中，在这种情况下没有递归。我几乎可以肯定，对于“正确”的输入，您的功能可以永远不会 return。找出这些案例并记录下来。在这两者之间，您遇到了 return 经过有限步数的情况。如果你完全不知道如何分析它们，你总是可以设置一个基准和衡量标准。测量输入大小 10、50、100、1000 的运行时间应该足以区分线性、二次和对数依赖。

PS：提示：不要忘记代码实际上应该做什么以及解决该问题需要什么时间复杂度（通常更容易以抽象的方式讨论而不是而不是深入研究代码）。在上面这个愚蠢的例子中，整个函数可以用它的等价物 int foo(int){ return 0; } 代替，它显然具有恒定的复杂性，不需要比它更复杂。

Answer 3

此函数采用有向图和该图中的一个顶点，并向后追逐进入其中的边以找到没有边指向其中的顶点。查找任何给定顶点“后面”的顶点的操作需要 O(n) 字符串比较 n 图中 k/v 对的数量（这是 for 循环）。它执行 m 次，其中 m 是它必须遵循的路径的长度（它通过递归执行）。因此，它具有时间复杂度 O(m * n) 字符串比较 n k/v 对的数量和 m 路径的长度。

请注意，对于您在代码中看到的某些函数，通常没有“时间复杂度”这样的东西。您必须定义要用来描述时间的变量，以及要用来测量时间的操作。例如。如果我们想纯粹根据 n k/v 对的数量来写这个，你运行就会遇到问题，因为如果图形包含适当放置的循环，函数 不终止！ 如果你进一步约束图是非循环的，那么任何路径的最大长度被m < n约束，然后您还可以得到该函数对具有 n 条边的无环图进行 O(n^2) 字符串比较。

如何计算以下函数的时间复杂度？

How do I calculate the time complexity of the following function?

c++

time-complexity