MickyOr

Ejemplos para analisis de complejidad

Aug 4th, 2021
700
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.   {
  7.     // O(1)
  8.     int a = 1, b = 2;
  9.     int c = a + b;    
  10.   }
  11.   {
  12.     // O(n)
  13.     int n;
  14.     cin >> n;
  15.     int res = 0;
  16.     for (int i = 0; i < n; i++) {
  17.       res = res + i;
  18.     }
  19.     cout << res << endl;
  20.   }
  21.   {
  22.     // O(n^2)
  23.     int n;
  24.     cin >> n;
  25.     int res = 0;
  26.     for (int i = 0; i < n; i++) {
  27.       for (int j = 0; j < n; j++) {
  28.         res = res + i*j;
  29.       }
  30.     }
  31.     cout << res << endl;
  32.   }
  33.   {
  34.     // O(n)
  35.     int n;
  36.     cin >> n;
  37.     int res = 0;
  38.     for (int i = 0; i < 3*n; i++) {
  39.       res = res + i%3;
  40.     }
  41.     cout << res << endl;
  42.   }
  43.   {
  44.     // O(n^3)
  45.     int n;
  46.     cin >> n;
  47.     int res = 0;
  48.     for (int i = 0; i < n; i++) {
  49.       for (int j = 0; j < n; j++) {
  50.         res = res - i*j;
  51.       }
  52.       for (int j = 0; j < n; j++) {
  53.         for (int k = 0; k < n; k++) {
  54.           res = res + i*(j-k);
  55.         }
  56.       }
  57.     }
  58.     cout << res << endl;
  59.   }
  60.   {
  61.     // O(n^2)
  62.     int n;
  63.     cin >> n;
  64.     int res = 0;
  65.     for (int i = 0; i < n; i++) {
  66.       for (int j = i+1; j < n; j++) {
  67.         res++;
  68.       }
  69.     }
  70.     cout << res << endl;
  71.   }
  72.   {
  73.     // O(1)
  74.     vector<int> v;
  75.     v.push_back(24);
  76.   }
  77.   {
  78.     // O(logn)
  79.     set<int> s;
  80.     s.insert(25);
  81.   }
  82.   {
  83.     // O(n*logn)
  84.     int n;
  85.     cin >> n;
  86.     set<int> s;
  87.     for (int i = 0; i < n; i++) {
  88.       s.insert((2*i + i/3) % n);
  89.     }
  90.     cout << s.size() << '\n';
  91.   }
  92.   return 0;
  93. }
RAW Paste Data