递归函数没有特定停止规则时的时间复杂度

Question

这是一个递归函数。它遍历字符串映射（multimap

string findOriginalExp(string Exp){
    cout<<"*****findOriginalExp Function*****"<<endl;
    for(auto itr=graph.begin();itr!=graph.end();itr++){
        string s_tmp = itr->second;
        string f_tmp = itr->first;
        string nll = "null";

        if(s_tmp.compare(Exp) == 0){
            if(f_tmp.compare(nll) == 0){
                cout<< Exp <<" :is original experience.";
                return Exp;
             }else{
                return findOriginalExp(itr->first);
             }
        } 
    }
}

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




Answer 1

匿名用户

您的代码相当于以下代码，我发现这些代码更具可读性：

std::string findOriginalExp(std::string Exp)
{
    std::cout << "*****findOriginalExp Function*****" << std::endl;
    auto it = std::find_if(graph.begin(), graph.end(), [&](auto& p){ return p.second == Exp; });
    // assert(it != graph.end());
    if (it->first == "null") {
        std::cout << Exp << " :is original experience.";
        return Exp;
    }
    return findOriginalExp(it->first);
}

对于复杂性：

• 你复制Exp:O（M）
• 你做了一个线性搜索（带字符串），所以O（NxM），
• 和递归调用

具有

• 图的大小

除非存在无限循环，否则递归调用计数最深的将是图的大小（基本上是一棵树并试图找到根，所以最长的将是一个列表）

结果将是O（N²xM）。

Answer 2

问题是：你的功能不正确。除非您对图的内容有非常特殊的先决条件（您没有告诉我们），否则您的代码将调用未定义的beahvior。

也许编译器比我更能说服你。我在你的代码中添加了缺失的部分来得到这个：

#include <string>
#include <map>
#include <iostream>

using namespace std;

std::map<std::string,std::string> graph;

string findOriginalExp(string Exp){
    cout<<"*****findOriginalExp Function*****"<<endl;
    for(auto itr=graph.begin();itr!=graph.end();itr++){
        string s_tmp = itr->second;
        string f_tmp = itr->first;
        string nll = "null";

        if(s_tmp.compare(Exp) == 0){
            if(f_tmp.compare(nll) == 0){
                cout<< Exp <<" :is original experience.";
                return Exp;
             }else{
                return findOriginalExp(itr->first);
             }
        } 
    }
}

int main(int argc, char *argv[]){
}

并尝试使用gcc编译它-Werror会产生以下错误：

<source>: In function 'std::string findOriginalExp(std::string)':
<source>:25:1: error: control reaches end of non-void function [-Werror=return-type]
   25 | }
      | ^
cc1plus: all warnings being treated as errors
ASM generation compiler returned: 1
<source>: In function 'std::string findOriginalExp(std::string)':
<source>:25:1: error: control reaches end of non-void function [-Werror=return-type]
   25 | }
      | ^
cc1plus: all warnings being treated as errors
Execution build compiler returned: 1

不从声明为返回某些内容的函数返回某些内容是未定义的行为。在存在未定义行为的情况下，您的代码可能看起来可以工作，但它仍然被破坏。

讨论该函数的时间复杂度是没有意义的（除非您包含了一些前提条件，以确保在考虑事项中实际上不会遇到未定义的行为）。