Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std ;
- map<int,string> m ;
- double processor_unit_time ;
- double observed_time ;
- const int MAXN = 1e6 ;
- vector<int>a( MAXN ) ;
- #define FOR(i, n) for (int i = 0; i < n; i++)
- int n, t[4*MAXN];
- #define ff first
- #define ss second
- int cnt[ 50 ] ;
- void Complexity_calculator ( double N )
- {
- double mi = 1e9 ;
- int idx ;
- double T[11] ;
- T[1] = N*processor_unit_time ; // O( N ) complexity
- T[2] = N*log2(N)*processor_unit_time ; // O( N*log2(N) )
- T[3] = N*N*processor_unit_time ; // O( N*N )
- T[4] = N*N*log2(N)*processor_unit_time; // O(N*N*log2(N))
- T[5] = log2(N)*processor_unit_time ;
- T[6] = N*N*N*processor_unit_time ;
- T[7] = N*N*N*N*processor_unit_time ;
- T[8] = sqrt(N)*processor_unit_time ;
- T[9] = sqrt(N)*N*processor_unit_time ;
- T[10] = N*N*sqrt( N )*processor_unit_time ;
- for( int i = 1 ; i <= 10 ; i ++ )
- {
- T[i] = T[i];
- cout<<T[i]<<endl ;
- if( abs(T[i] - observed_time) < mi )
- {
- mi = abs(T[i] - observed_time) ;
- idx = i ;
- }
- }
- cout<<m[idx]<<endl;
- }
- void Complexity_calculator ( double N , double observed_time )
- {
- double mi = 1e9 ;
- int idx ;
- double T[12] ;
- T[1] = N*processor_unit_time ; // O( N ) complexity
- T[2] = N*log2(N)*processor_unit_time ; // O( N*log2(N) )
- T[3] = N*N*processor_unit_time ; // O( N*N )
- T[4] = N*N*log2(N)*processor_unit_time; // O(N*N*log2(N))
- T[5] = log2(N)*processor_unit_time ;
- T[6] = N*N*N*processor_unit_time ;
- T[7] = N*N*N*N*processor_unit_time ;
- T[8] = sqrt(N)*processor_unit_time ;
- T[9] = sqrt(N)*N*processor_unit_time ;
- T[10] = N*N*sqrt( N )*processor_unit_time ;
- T[11] = N*log2(log2(N))*processor_unit_time ; // O( N*log2(N) )
- for( int i = 1 ; i <= 11 ; i ++ )
- {
- T[i] = T[i];
- // cout<<T[i]<<endl ;
- if( abs(T[i] - observed_time) < mi )
- {
- mi = abs(T[i] - observed_time) ;
- idx = i ;
- }
- }
- cnt[idx]++ ;
- // cout<<m[idx]<<endl;
- }
- void pre( )
- {
- const clock_t begin_time = clock();
- for( int i = 1 ; i <= MAXN ; i ++ ) ;
- double k = float( clock () - begin_time ) / CLOCKS_PER_SEC;
- processor_unit_time = k/MAXN ;
- m[ 1 ] = "O(N)" ;
- m[ 2 ] = "O( N* Log(N) )" ;
- m[ 3 ] = "O( N^2 )" ;
- m[ 4 ] = "O( N^2 * Log(N) )" ;
- m[ 5 ] = "O( Log(N) )" ;
- m[ 6 ] = "O( N^3 ) " ;
- m[ 7 ] = "O( N^4 ) " ;
- m[ 8 ] = "O( sqrt(N) )" ;
- m[ 9 ] = "O( N * sqrt(N) )" ;
- m[ 10 ] = "O( N^2 * sqrt(N) ) ";
- m[ 11 ] = "O( N* Log(log(N) )" ;
- }
- int main( )
- {
- // int n ;
- freopen("Seive_NLOGN.out", "r", stdin);
- vector<pair<double,double> > A( 1000 );
- FOR( i, 1000 )cin>>A[i].ff>>A[i].ss ;
- pre() ;
- FOR( i , 1000 )
- Complexity_calculator( A[i].ff , A[i].ss ) ;
- int ma = 0 ;
- int maidx = 0 ;
- FOR( i , 12 )
- {
- if( cnt[i] > cnt[maidx] )
- maidx = i ;
- // cout<<" "<<cnt[i]<<" " << m[i]<<endl ;
- }
- cout<<"Probable Complexity of Your Algorithm is "<<m[maidx]<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement