计蒜客 时间复杂度 (模拟) & 洛谷 P3952 时间复杂度

---

链接 : Here!

思路 :

• 这是一道大模拟, 区分好情况就没问题了

• 循环构成部分 : $F , x , i , j$ 和 $E$ , 需要注意的是 $i , j$,

  - 分析 $i, j$ 的情况 : 
        - 当 $i, j$ 全为 $n$ 的时候, 复杂度为 $O(1)$
        - 当 $i, j$ 为 $number$ 和 $n$ 的时候复杂度为 $O(n)$
        - 当 $i, j$ 为 $n$ 和 $number$ 的时候复杂度为 $O(0)$
        - 当 $i, j$ 全为 $number$ 时, 需要考虑
              - 如果 $i > j$ 复杂度为 $O(0)$
              - 否则复杂度为 $O(1)$
  

• 分析多个循环的复杂度情况 :
  - 首先分析循环内外层嵌套的复杂度情况 :

     - | 外层复杂度 \\ 内层复杂度 | O(0)         | O(1)         | O($n^{w_2}$)                         |
  | -------------- | ------------ | ------------ | ------------------------------------ |
  | O(0)           | O(0)         | O(0)         | O(0)                                 |
  | O(1)           | O(1)         | O(1)         | O(n)                                 |
  | O($n^{w_1}$)   | O($n^{w_1}$) | O($n^{w_1}$) | multiply(O($n^{w_1}$), O($n^{w_2}$)) |
   
  - 然后**分析循环并列**的复杂度情况 : **选取并列复杂度较大的那个**
  

• 错误情况 :
  - $F$ 和 $E$ 不匹配
  - 预期复杂度与实际复杂度不匹配

• 分析完成之后直接敲代码就$ok$了, 如果我们将整个大的循环嵌套并列的结构抽象成一棵树的话, 那就会发现, 必须存一下当前层的最大复杂度

  ​

代码 :

/*************************************************************************
    > File Name: 时间复杂度.cpp
    > Author: 
    > Mail: 
    > Created Time: 2017年11月22日 星期三 18时26分04秒
 ************************************************************************/
 
#include <cstdio>
#include <iostream>
#include <string>
#include <stack>
using namespace std;
 
struct expr {
    char var;         // 记录变量名 
    string st, ed;    // 记录循环的开始终止位置
    string tempO;     // 记录复杂度
    string nowLayerO; // 记录当前层的最大复杂度
};
int T, n;
string des; // 记录预测复杂度
 
int calNumber(const string &str) {
    int temp = 0;
    for (int i = 0 ; i < str.length() ; ++i) {
        temp = temp * 10 + str[i] - '0';
    }
    return temp;
}
 
// 计算复杂度
void calComplexity(expr &exp) {
    // case 1 : 如果st,ed全为n的话
    if (exp.st == "n" && exp.ed == "n") {
        exp.tempO = "1";
        return;
    }
    // case 2 : 如果st为数字,ed为n 
    if (exp.st != "n" && exp.ed == "n") {
        exp.tempO = "n";
        return;
    }
    // case 3 : 如果st为n,ed为数字
    if (exp.st == "n" && exp.ed != "n") {
        exp.tempO = "0";
        return;
    }
    // case 4 : 如果st,ed全为数字且st <= ed
    // case 5 : 如果st,ed全为数字且st >  ed
    int st_num = calNumber(exp.st); 
    int ed_num = calNumber(exp.ed);
    if (st_num <= ed_num) {
        exp.tempO = "1";
    } else {
        exp.tempO = "0";
    }
    return;
}
 
// 计算str中的幂指数, str为n^w(w >= 1),当w为1的时候是可以省略的
int calExponent(const string &str) {
    // 特殊情况
    if (str == "n") {
        return 1;
    }
    int ret = 0;
    for (int i = 2 ; i < str.length() ; ++i) {
        ret = ret * 10 + str[i] - '0';
    }
    return ret;
}
 
// 复杂度相乘
// 如果外层循环是O(0)那么a * b -> O(0)
// 如果内层循环是O(0)那么a * b -> a的复杂度
// a代表外层复杂度, b代表内层复杂度
string multiComplexity(const string &a, const string &b) {
    string ret = "";
    if (a == "0") {
        ret = "0";
    } else if (a == "1") {
        if (b == "0") {
            ret = "1";
        } else {
            ret = b;
        }
    } else {
        if (b == "0") {
            ret = a;
        } else if (b == "1") {
            ret = a;
        } else {
            // 如果能进入这里首先可以确定a,b为n^w
            // 且a,b的w >= 1因此tstr直接写个前缀n^是完全没问题的
            int expon1 = calExponent(a);
            int expon2 = calExponent(b);
            string tstr1 = "n^";
            string tstr2 = "";
            expon1 += expon2;
            while (expon1) {
                tstr2 += (char)((expon1 % 10) + '0');
                expon1 /= 10;
            }
            for (int i = tstr2.length() - 1 ; i >= 0 ; --i) {
                tstr1 += tstr2[i];
            }
            ret = tstr1;
        }
    }
    return ret;
}
 
// 复杂度相加,选出复杂度较大的那个
string addComplexity(const string &a, const string &b) {
    string ret = "";
    if (a == "0") {
        ret = b;
    } else if (a == "1") {
        ret = (b == "0" ? a : b);
    } else {
        if (b == "0" || b == "1") {
            ret = a;
        } else {
            int expon1 = calExponent(a);
            int expon2 = calExponent(b);
            ret = (expon1 > expon2 ? a : b);
        }
    }
    return ret;
}
 
void read() {
    scanf("%d", &T);
    while (T--) {
        int vis[30] = {0}, flag = 0;     // 标记是否出现变量名冲突
        cin >> n >> des;
        expr exp[n];
        stack<expr> myStack;
        string sum = "0";
        string maxO = "0";
        for (int i = 0 ; i < n ; ++i) {
            char firstCh;
            cin >> firstCh;
            if (firstCh != 'E') {
                cin >> exp[i].var >> exp[i].st >> exp[i].ed;
                if (vis[exp[i].var - 'a']) {
                    flag = 1;
                }
                vis[exp[i].var - 'a'] = 1;
                calComplexity(exp[i]);
                // cout << "exp.tempO : " << exp[i].tempO << endl;
                exp[i].nowLayerO = exp[i].tempO;
                myStack.push(exp[i]);
            } else {
                // 如果遇到E则该弹栈计算了 
                // 并且更新新栈顶当前层数最大复杂度
                // 如果空栈还弹,那说明ERR
                if (myStack.empty()) {
                    flag = 1;
                    continue;
                }
                expr topExp = myStack.top(); 
                myStack.pop();
                vis[topExp.var - 'a'] = 0;
                // 先获取当弹出的当前层最大复杂度
                string temp1 = topExp.nowLayerO;
                // 暂存一下当前最大复杂度
                maxO = topExp.nowLayerO;
 
                // 如果能向上更新这个最大复杂度
                if (!myStack.empty()) {
                    topExp = myStack.top();
                    myStack.pop();
 
                    topExp.nowLayerO = addComplexity(topExp.nowLayerO, multiComplexity(topExp.tempO, temp1));
                    
                    myStack.push(topExp);
                }
                // cout << " maxO : " << maxO << endl;
            }
            // 如果栈为空,那么说一个loop已经结束了
            if (myStack.empty()) {
                sum = addComplexity(sum, maxO);
                maxO = "0";
            }
        }
        if (flag || !myStack.empty() || (n & 1)) {
            printf("ERR\n");
        } else {
            // cout << "ans : " << sum << endl;
            if (sum == "n") sum = "n^1";
            if (sum == "0") sum = "1";
            sum = "O(" + sum + ")";
            if (sum == des) {
                printf("Yes\n");
            } else {
                printf("No\n");
            }
        }
    }
}
int main() {
    read();
    return 0;
}