C++를  공부하고있는 고등학생입니다 !

 

시간복잡도에 대해 아직 안배워서 잘모르는데

 

혹시 이코드의 시간복잡도좀 알려주실 수 있을까요 ???

 

가능하시다면 이유도 좀 알려주셨으면 좋겠습니다 !

 

 

#include <iostream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
using namespace std;
 
const int maxn = 100000+10;
 
long long tree[maxn];
int arr[maxn];
int input[maxn];
long long n,sum;
 
int psum(int pos){
    ++pos;
    if(pos <= 0) return 0;
    long long ret=0;
    
    while(pos>0){
        ret += tree[pos];
        pos &= (pos-1);
    }
    return ret;
}
 
void add(int pos){
    ++pos;
    while(pos < n){
        tree[pos]++;
        pos += (pos&-pos);
    }
}
 
int main(){
  
 int t,t1;
 cin >>t;
 t1=t;

 int array[maxn];

    while(t--){
        memset(tree,0,sizeof(tree));
        memset(arr,0,sizeof(arr));
        memset(input,0,sizeof(input));
        
        sum=0;
        
        cin >> n;
        
        for(int i=0; i<n; i++) cin >> input[i];
        for(int i=0; i<n; i++) {int x; cin >> x; arr[x] = i;}
        
        for(int i=0; i<n; i++)    // 복잡도가  O(n * logn)
        {
            int that = arr[input[i]];
            sum += that - psum(that-1);
            add(that);
         
  }
   array[t]=sum;
      
    }
 for(int i=0;i<t1;i++) {
  printf("%lld\n",array[t1-i-1]);
 
 }
}