Advertisement
Guest User

Untitled

a guest
Apr 26th, 2017
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3. map<int,string> m ;
  4. double processor_unit_time ;
  5. double observed_time ;
  6. const int MAXN = 1e6 ;
  7. vector<int>a( MAXN ) ;
  8. #define FOR(i, n) for (int i = 0; i < n; i++)
  9. int n, t[4*MAXN];
  10. #define ff first
  11. #define ss second
  12. int cnt[ 50 ] ;
  13.  
  14.  
  15. void Complexity_calculator ( double N )
  16. {
  17. double mi = 1e9 ;
  18. int idx ;
  19. double T[11] ;
  20.  
  21. T[1] = N*processor_unit_time ; // O( N ) complexity
  22. T[2] = N*log2(N)*processor_unit_time ; // O( N*log2(N) )
  23. T[3] = N*N*processor_unit_time ; // O( N*N )
  24. T[4] = N*N*log2(N)*processor_unit_time; // O(N*N*log2(N))
  25. T[5] = log2(N)*processor_unit_time ;
  26. T[6] = N*N*N*processor_unit_time ;
  27. T[7] = N*N*N*N*processor_unit_time ;
  28. T[8] = sqrt(N)*processor_unit_time ;
  29. T[9] = sqrt(N)*N*processor_unit_time ;
  30. T[10] = N*N*sqrt( N )*processor_unit_time ;
  31.  
  32. for( int i = 1 ; i <= 10 ; i ++ )
  33. {
  34. T[i] = T[i];
  35. cout<<T[i]<<endl ;
  36. if( abs(T[i] - observed_time) < mi )
  37. {
  38. mi = abs(T[i] - observed_time) ;
  39. idx = i ;
  40. }
  41. }
  42.  
  43. cout<<m[idx]<<endl;
  44.  
  45. }
  46.  
  47. void Complexity_calculator ( double N , double observed_time )
  48. {
  49. double mi = 1e9 ;
  50. int idx ;
  51. double T[12] ;
  52.  
  53. T[1] = N*processor_unit_time ; // O( N ) complexity
  54. T[2] = N*log2(N)*processor_unit_time ; // O( N*log2(N) )
  55. T[3] = N*N*processor_unit_time ; // O( N*N )
  56. T[4] = N*N*log2(N)*processor_unit_time; // O(N*N*log2(N))
  57. T[5] = log2(N)*processor_unit_time ;
  58. T[6] = N*N*N*processor_unit_time ;
  59. T[7] = N*N*N*N*processor_unit_time ;
  60. T[8] = sqrt(N)*processor_unit_time ;
  61. T[9] = sqrt(N)*N*processor_unit_time ;
  62. T[10] = N*N*sqrt( N )*processor_unit_time ;
  63. T[11] = N*log2(log2(N))*processor_unit_time ; // O( N*log2(N) )
  64. for( int i = 1 ; i <= 11 ; i ++ )
  65. {
  66. T[i] = T[i];
  67. // cout<<T[i]<<endl ;
  68. if( abs(T[i] - observed_time) < mi )
  69. {
  70. mi = abs(T[i] - observed_time) ;
  71. idx = i ;
  72. }
  73. }
  74.  
  75. cnt[idx]++ ;
  76. // cout<<m[idx]<<endl;
  77.  
  78. }
  79.  
  80. void pre( )
  81. {
  82.  
  83.  
  84. const clock_t begin_time = clock();
  85. for( int i = 1 ; i <= MAXN ; i ++ ) ;
  86. double k = float( clock () - begin_time ) / CLOCKS_PER_SEC;
  87. processor_unit_time = k/MAXN ;
  88.  
  89. m[ 1 ] = "O(N)" ;
  90. m[ 2 ] = "O( N* Log(N) )" ;
  91. m[ 3 ] = "O( N^2 )" ;
  92. m[ 4 ] = "O( N^2 * Log(N) )" ;
  93. m[ 5 ] = "O( Log(N) )" ;
  94. m[ 6 ] = "O( N^3 ) " ;
  95. m[ 7 ] = "O( N^4 ) " ;
  96. m[ 8 ] = "O( sqrt(N) )" ;
  97. m[ 9 ] = "O( N * sqrt(N) )" ;
  98. m[ 10 ] = "O( N^2 * sqrt(N) ) ";
  99. m[ 11 ] = "O( N* Log(log(N) )" ;
  100.  
  101. }
  102. int main( )
  103. {
  104. // int n ;
  105. freopen("Seive_NLOGN.out", "r", stdin);
  106. vector<pair<double,double> > A( 1000 );
  107. FOR( i, 1000 )cin>>A[i].ff>>A[i].ss ;
  108. pre() ;
  109. FOR( i , 1000 )
  110. Complexity_calculator( A[i].ff , A[i].ss ) ;
  111.  
  112. int ma = 0 ;
  113. int maidx = 0 ;
  114. FOR( i , 12 )
  115. {
  116. if( cnt[i] > cnt[maidx] )
  117. maidx = i ;
  118. // cout<<" "<<cnt[i]<<" " << m[i]<<endl ;
  119. }
  120.  
  121. cout<<"Probable Complexity of Your Algorithm is "<<m[maidx]<<endl;
  122.  
  123.  
  124.  
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement