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

Question

这里是一个递归函数。它遍历字符串映射(multimap graph )。检查itr->second(s_tmp)如果s_tmp等于所需的字符串(exp)，则打印它(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);
}

在最坏的情况下，它永远不会返回给调用者。如果我们忽略x>=42，那么最坏情况的复杂性是O(n)。单凭这一点对于用户来说并不是那么有用的信息。作为用户，我真正需要知道的是：

• 不要使用x>=42调用它。
• O(1)如果x==0
• O(x)如果x>0
• O(ln(x))如果x<0

现在试着为您的函数做类似的考虑。最简单的情况是exp不在graph中，在这种情况下没有递归。我几乎可以肯定的是，对于“正确的”输入，您的函数将永远不会返回。找出那些是什么案子并记录下来。在这两者之间，您有在有限的步骤后返回的案例。如果你没有任何线索，如何得到您的手的分析，您可以始终建立一个基准和衡量。正在测量输入大小10、50、100、1000的运行时。应足以区分线性、二次和对数依赖关系。

PS：只是一个提示：不要忘记代码实际上应该做什么，以及需要多长时间来解决这个问题（通常更容易以抽象的方式来讨论，而不是深入到代码中）。在上面这个愚蠢的例子中，整个函数可以被其等价的int foo(int){return0；}替换，它显然具有恒定的复杂性，并且不需要比它更复杂。