c++ - 解决这个问题的时间复杂度是多少？

Question

问题:

https://www.spoj.com/problems/BALNUM/

我的解决方案:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
vector<ll>v;
ll dp[20][2][3][3][3][3][3][3][3][3][3][3][2];
ll solve(ll i,ll less,ll start,ll m0,ll m1,ll m2,ll m3,ll m4,ll m5,ll m6,ll m7,ll m8,ll m9){
  if(i == s.size()){
    if((m1 == 2 or m1 == 0) and (m3 == 2 or m3 == 0) and (m5 == 2 or m5 == 0) and (m7 == 2 or m7 == 0) and (m9 == 2 or m9 == 0) and (m0 == 1 or m0 == 0) and (m2 == 1 or m2 == 0) and (m4 == 1 or m4 == 0) and (m6 == 1 or m6 == 0) and (m8 == 1 or m8 == 0)){
      return 1;
    }
    return 0;
  }
  ll &ret = dp[i][less][m0][m1][m2][m3][m4][m5][m6][m7][m8][m9][start];
  if(ret != -1) return ret;
  ll k = less ? 9 : v[i];
  ll ans = 0;
  for(ll j = 1; j <= k; j++){
    if(j == 1){
      ans += solve(i+1,less | (j < v[i]),0,m0,((m1+1)%3 == 0) ? 1:(m1+1)%3,m2,m3,m4,m5,m6,m7,m8,m9);
    }else if(j == 2){
      ans += solve(i+1,less | (j < v[i]),0,m0,m1,((m2+1)%3 == 0) ? 1:(m2+1)%3,m3,m4,m5,m6,m7,m8,m9);
    }else if(j == 3){
      ans += solve(i+1,less | (j < v[i]),0,m0,m1,m2,((m3+1)%3 == 0) ? 1:(m3+1)%3,m4,m5,m6,m7,m8,m9);
    }else if(j == 4){
      ans += solve(i+1,less | (j < v[i]),0,m0,m1,m2,m3,((m4+1)%3 == 0) ? 1:(m4+1)%3,m5,m6,m7,m8,m9);
    }else if(j == 5){
      ans += solve(i+1,less | (j < v[i]),0,m0,m1,m2,m3,m4,((m5+1)%3 == 0) ? 1:(m5+1)%3,m6,m7,m8,m9);
    }else if(j == 6){
      ans += solve(i+1,less | (j < v[i]),0,m0,m1,m2,m3,m4,m5,((m6+1)%3 == 0) ? 1:(m6+1)%3,m7,m8,m9);
    }else if(j == 7){
      ans += solve(i+1,less | (j < v[i]),0,m0,m1,m2,m3,m4,m5,m6,((m7+1)%3 == 0) ? 1:(m7+1)%3,m8,m9);
    }else if(j == 8){
      ans += solve(i+1,less | (j < v[i]),0,m0,m1,m2,m3,m4,m5,m6,m7,((m8+1)%3 == 0) ? 1:(m8+1)%3,m9);
    }else if(j == 9){
      ans += solve(i+1,less | (j < v[i]),0,m0,m1,m2,m3,m4,m5,m6,m7,m8,((m9+1)%3 == 0) ? 1:(m9+1)%3);
    }
  }

  if(!start){
    ans += solve(i+1,less | (0 < v[i]),0,((m0+1)%3 == 0) ? 1:(m0+1)%3,m1,m2,m3,m4,m5,m6,m7,m8,m9);
  }
  if(start){
    ans += solve(i+1,1,1,0,0,0,0,0,0,0,0,0,0);
  }
  return ret = ans;
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  ll t;
  cin>>t;
  while(t--){
    ll x;
    cin>>x;
    --x;
    s = to_string(x);
    memset(dp,-1,sizeof(dp));
    v.clear();
    for(char c:s) v.push_back(c-'0');
    ll a=solve(0,0,1,0,0,0,0,0,0,0,0,0,0);
    cin>>s;
    memset(dp,-1,sizeof(dp));
    v.clear();
    for(char c:s) v.push_back(c-'0');
    ll b=solve(0,0,1,0,0,0,0,0,0,0,0,0,0);
    cout<<b-a<<endl;
  }
}

这里我用于内存的数组是 dp[20][2][3][3][3][3][3][3][3][3][3][3][2 ](20是整数A或B的最大长度)

是时间复杂度 O(n) 具有非常高的常数(如 2*3*3*3*3*3*3*3*3*3*3*2)，其中 n 是整数 A 的最大长度还是乙？

Answer 1

它的 T * ( N * (2^2 * 3^10 * 9) + C )，常数因子确实很大，但总的来说我认为你可以说时间复杂度是 T * N * (一个巨大的常数因子)。

所以你可以说它是 O(T*N)。