时间复杂度题解

比某 @long_hao 的屑题解正经多了 ~~（傲娇脸~~

排版不咋地，凑合看罢——2022.5.2注

1. 题面简述

这是一道著名的毒瘤模拟，给定一个只有循环的程序，让你判断复杂度。

~~算了还是自己去看题吧~~

链接

2. 思路

循环的开始和结束很明显是符合栈的后进先出性质的。因此我们考虑用栈来模拟。

为了方便起见，这篇文章把一个循环自身所能贡献的复杂度称为基础复杂度。 常数复杂度以表示，的复杂度以表示，不会执行的循环的复杂度以表示。一个循环及其所有的子循环所能贡献的复杂度称为总复杂度。 表示规则相同。

在研究时，可以抽象出多个循环的两种组合方式，对于这两种不同的方式，计算时间复杂度时所需的计算方式也不同。

   	F i x y
   	F i x y
   	...
   	E
   	E

这种为基本的循环嵌套。

	F i x y
	...
	E
	F i x y
	...
	E

这种为 1 并列而成的结构。

既然要用栈计算时间复杂度，那么栈中至少要维护的一个元素就是当前循环的总复杂度了。

不难想到在模拟时，若遇到 F 操作，直接将基础复杂度入栈；若遇到 E 操作，如果当前循环可被执行的话就弹出并更新栈顶。

如何更新栈顶的总复杂度呢？对于第一种组合方式，很明显在可执行时直接加和即可。对于第二种组合方式，总复杂度应为各个子循环的最大值。

要动态更新第二种方式的总复杂度，我们还应在栈中维护该层循环的基础复杂度。这时若旧栈顶与新栈顶的总复杂度分别为，基础复杂度分别为，不难得到复杂度计算的公式。

这个公式亦可用于第一种方式的计算。因为在没有并列循环时，很明显有，则此时一定成立，所以这个公式等价于。因此我们只需判断在时执行这个公式即可。在时由于该层循环不执行，对复杂度没有贡献，因此不需要更新栈顶。

清楚如何计算复杂度以后，还有另外一个问题：判断语法是否正确。

其实也很简单。可以直接利用我们维护的栈判断。一个程序如果是错误的，那么它一定满足以下条件之一：

新增变量与已知变量冲突。可以打标记进行判定。
进行 E 操作时发现栈已空。
程序复杂度计算完后发现栈的大小不为 1。

第一个条件不必细说，后两个条件对应的是 F 和 E 不匹配的情况。

如果程序发现错误，则可以立即中断模拟。消耗掉输入流中的内容后再进行下一轮模拟。

另外，由于维护栈的原因，我们还需要在输入时计算一下基础复杂度。这可以用一点小技巧实现。可以将固定成一个较大的数（大于 200 即可）。输入时可以利用快读，若输入为 n 就直接替换成这个较大的数。若说明复杂度为；若说明复杂度为，剩下的情况即为。

最后一点问题是输入计算的复杂度时可以用字符串读入，再把复杂度抠出来。

可以加一个显而易见的小优化：如果行数为奇数那么程序肯定为错误的。

AC Code

#include <iostream>
#include <stack>
#include <cctype>
#include <cstring>
using namespace std;

const int MAXC = 140;
bool v[MAXC];
struct cir {
    int base, sum;
    char var;

    cir() {}

    cir(const int & base_, const int & sum_, const char & var_)
    {
        base = base_, sum = sum_, var = var_;
    }
};

const int read()
{
    int ans = 0;
    char c = getchar();
    while (isspace(c)) {
        c = getchar();
    }
    while (isdigit(c)) {
        ans *= 10;
        ans += c - '0';
        c = getchar();
    }
    if (c == 'n') { // 对快读进行一点更改，使其如果读入 n 就替换成 210
        ans = 210;
    }
    return ans;
}

void get(int & c) // 把复杂度抠出来
{
    string a;
    cin >> a;
    c = 0;
    if (a[2] == '1') {
        return;
    }
    int p = 4;
    while (isdigit(a[p])) {
        c *= 10;
        c += a[p] - '0';
        p++;
    }
    return;
}

void eatline()
{
    char c = getchar();
    while (c != '\n' && c != EOF) { c = getchar(); }
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        memset(v, 0, sizeof v);
        bool gram = true;
        int l, c;
        cin >> l;
        get(c);
        gram = !(l & 1);
        getchar(); // 如果要加小优化的话就必须要 getchar()，或者 eatline() 也行
        // 总之会有一个换行符必须吃掉，不然会影响下面 eatline() 函数的运作（少吃一行）
        stack<cir> st;
        st.push(cir(0, 0, 0));
        for (int i = 1; i <= l; i++) {
            if (!gram) { // 消耗输入流中剩余内容防止读入错误
                eatline();
                continue;
            }
            char a;
            cin >> a;
            if (a == 'F') {
                char var;
                cin >> var;
                if (v[var]) { // 语法错误条件一
                    gram = false;
                    eatline();
                    continue;
                }
                v[var] = true;
                int x = read(), y = read();
                int c;
                if (y - x > 100) {
                    c = 1;
                }
                else if (y - x < 0) {
                    c = -1;
                }
                else {
                    c = 0;
                }
                st.push(cir(c, c, var));
            }
            else if (a == 'E') {
                cir t = st.top();
                st.pop();
                if (st.empty()) {
                    gram = false; // 语法错误条件二
                    eatline();
                    continue;
                }
                if (t.base != -1) { // 更新栈顶元素
                    st.top().sum = max(st.top().sum, t.sum + st.top().base);
                }
                v[t.var] = false; // 解除变量标记
            }
            else { // 这个是调试读入是否错误用的
                cout << "ERROR " << a << endl;
                cout << "I: " << i << endl;
            }
        }
        if (st.size() != 1) { // 语法错误条件三
            gram = false;
        }
        if (!gram) {
            cout << "ERR" << endl;
        }
        else if (st.top().sum != c) {
            cout << "No" << endl;
        }
        else {
            cout << "Yes" << endl;
        }
    }
    return 0;
}

1. 题面简述

2. 思路

AC Code

共 1 条回复