if-语句和while循环嵌套的for循环的时间复杂性。

Question

void makeGraph(){
    for(auto itr = inputs.begin(); itr != inputs.end(); itr++){
        string str = itr->second;
        if (strstr(str.c_str(), "->") != NULL){
            char ch = '>';
            size_t pos = str.find_last_of(ch);
            parent = str.substr(0, pos-2);
            string child = str.substr(pos+2);
            if (strstr(parent.c_str(), ",") != NULL){
                int size_parent = parent.length();
                char ch_parent[size_parent+1];
                strcpy(ch_parent, parent.c_str());
                char *token = strtok(ch_parent, ",");
                while (token != NULL){
                    string sub_Parent = token;
                    sub_Parent.erase(std::remove(sub_Parent.begin(),
                                                 sub_Parent.end(),
                                                 ' '),
                                     sub_Parent.end());
                    graph[sub_Parent].push_back(child);
                    token = strtok(NULL, ",");
                }
            } else{
                graph[parent].push_back(child);
            }
        } else{
            cout<<"Just for TEST"<<endl;
        }
    }
    printGraph();
}

这个函数的时间复杂度是多少？是吗？如何处理the语句中的循环？

Answer 1

在这种情况下，困难在于您有许多需要考虑的变量。重要的是：

input.

• For中的元素数( input中的每个字符串)，字符串中的字符数.

如果您想要一个精确的估计，您将不得不分别说明这些变量。如果使用N来引用input的长度，那么N字符串的长度为M1、M2、.、MN。每个字符串可以以不同的方式处理，这样也会使事情复杂化。

由于Big-O提供了一个上限，因此我们可以通过考虑以下变量来省去一些麻烦：

1. N，是input.
2. M，中的元素数，是最长输入字符串的长度。

最后一个大的简化来自于观察最坏的情况行为。如果没有对输入数据的更多了解，我们就无法进行更细致的计算，所以让我们来做最坏的情况。

因为这里发生了很多事情，所以我喜欢看“叶子”--最嵌套的块--然后再往上爬。让我们磨练一下房间里的大象：while循环。这里发生了什么事？循环本身基本上只是在parent上迭代。注意，parent的长度可以与str的长度成线性关系，这意味着while循环的复杂性将类似于O(M * [complexity of the while body])。该机构仅由几个步骤组成：

string sub_Parent = token;
sub_Parent.erase(std::remove(sub_Parent.begin(), sub_Parent.end(), ' '), sub_Parent.end());
graph[sub_Parent].push_back(child);
token = strtok(NULL, ",");

涉及sub_Parent和token的工作涉及到while循环的循环行为(即，while循环迭代越少，token通常就越长，反之亦然)。但是，这些操作都不会比O(M)更糟糕，因为parent的长度本身就是O(M)。相反，让我们关注push_back()调用。因为child的长度是O(M)，而且由于这个push_back()复制了child，所以这个操作在时间复杂度上是O(M)。因此，我们可以肯定地说，并发循环体的复杂性也是O(M)。将主体与循环本身相结合，while循环的总复杂性是：

  O(M * [complexity of the while body]
= O(M * M)
= O(M^2)

现在让我们上升一级。while循环之外的操作显然是O(M)，因为它们处理parent的复制和搜索。while循环占主导地位，因此我们可以忽略这些贡献。

再往上走一层，我们就撞上了if。我们在这里做什么？在true的例子中，我们得到了复杂O(M^2)的while循环。在false的例子中，我们得到了一个带有child副本的push_back()，生成了O(M)。因为我们看到的是最坏的情况，我们会说if/else的复杂性是更大的表达式：O(M^2)。

在另一个级别上(就在上一步的if之外)，我们有一个类似的情况，即操作在最坏的情况下是O(M)，因为它们搜索和复制str来创建parent和child。这些都是由if复杂性主导的，因此我们可以忽略它们的贡献。

现在是最外层的if。我们再比较一下树枝。在true分支中，我们有我们刚刚计算出来的O(M^2)复杂性。在false分支中，我们有O(1)复杂性(只需要打印一个常量字符串)。因此，在最坏的情况下，这个if具有O(M^2)复杂性。

我们快到了。在那个if之外，我们有一个副本来创建str。这是O(M)，所以我们可以忽略它，因为它被来自if的O(M^2)所主导。因此，for循环体总共是O(M^2)。

最后，我们看一下for循环本身。它是input上的一个简单的线性迭代(长度为N元素)，这意味着它的复杂性是：

  O(N * [complexity of the body])
= O(N * M^2)

所以你就有了。最坏的情况复杂度在input的长度是线性的，而在最长的字符串的长度是二次的。