---

鏈接 : 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 > edint 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則該彈棧計算了 // 并且更新新棧頂當前層數最大復雜度// 如果空棧還彈,那說明ERRif (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; }

轉載于:https://www.cnblogs.com/WArobot/p/7884386.html

總結

以上是生活随笔為你收集整理的计蒜客 时间复杂度 (模拟) 洛谷 P3952 时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。