for循环嵌套if语句和while循环的时间复杂度

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();
}

这个函数的时间复杂度是多少？是n O(n)吗？？你如何处理 else 语句中的循环？

Answer 1

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

input中的元素个数。
对于input中的每个字符串，字符串中的字符数。

如果你想要一个精确的估计，你将不得不分别考虑这些变量中的每一个。如果我们用 N 来引用 input 的长度，那么我们有 N 个长度为 M1, M2, ..., MN。可以对每个字符串进行不同的处理，因此也使事情复杂化。

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

N，即input.
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 循环迭代次数越少，[= =31=] 一般都会，反之亦然）。然而，none 的这些操作将比 O(M) 更糟糕，因为 parent 的长度本身就是 O(M)。相反，让我们关注 push_back() 调用。由于child的长度是O(M)，并且由于这个push_back()复制了child，所以这个操作的时间复杂度是O(M)。因此，我们可以自信地说 while 循环体的复杂度也是 O(M)。将主体与循环本身结合起来，while 循环的总复杂度为：

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

现在让我们更上一层楼。 while 循环之外的操作显然是 O(M)，因为它们涉及复制和搜索 parent。 while 循环主导了这一点，因此我们可以忽略这些贡献。

再往上一层，我们到达 if。我们在这里做什么？那么，在 true 的情况下，我们得到 while 复杂度为 O(M^2) 的循环。在 false 的情况下，我们得到一个 push_back() 和 child 的副本，使得 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 的长度上是线性的，但在最长字符串的长度上是二次的。

for循环嵌套if语句和while循环的时间复杂度

The time complexity of the for loop nested with if-statement and while loop

c++

time-complexity