Testy

Asymptotické složitosti

Seznam všech otázek

1. Kolikrát se zavolá funkce foo ()? for (i = 0; i < 2 * n; i += 2) for (j = i; j < n; j++) foo ();

   `O(n)`
   `O(n^2)`
   `O(\log(n))`
   `O(n * \log (n))`

2. Kolikrát se zavolá funkce foo ()? for (i = 2; i <= n; i *= i) for (j = 0; j < n; j++) foo ();

   `O(n*\log(\log(n)))`
   `O(\log(\log(n)))`
   `O(n*(\log(n)))`
   `O(n^3)`

3. Kolikrát se zavolá funkce foo ()? for (i = 0; i < 2 * n; i += 2) for (j = n; j > i; j--) foo ();

   `O(n)`
   `O(n^2)`
   `O(n^3)`
   `O(2^n)`

4. Kolikrát se zavolá funkce foo ()? for (i = n; i >= 0; i -= 2) for (j = i; j > n; j--) foo ();

   `O(0)`
   `O(1)`
   `O(n)`
   `O(2 * n)`

5. Kolikrát se zavolá funkce foo ()? for (i = 1; i < n; i *= 2) for (j = n; j > 0; j /= 3) foo ();

   `O(\log(n)*\log(n))`
   `O(\log(n))`
   `O(n*\log(n))`
   `O(n*\log(\log(n)))`

6. Kolikrát se zavolá funkce foo ()? for (i = n; i != 0; i /= -3) for (j = 0; j < i * i * i; j++) foo ();

   `O(n)`
   `O(n^2)`
   `O(n^3)`
   `O(e^n)`

7. Kolikrát se zavolá funkce foo ()? for (i = n; i >= 0; i--) if (i < n / 2) for (j = i; j < n; j++) foo (); else for (j = i; j > 0; j--) foo ();

   `O(n)`
   `O(n^2)`
   `O(n^3)`
   `O(e^n)`

8. Kolikrát se zavolá funkce foo ()? for (i = 1; i < (n >> i); i++) foo();

   `O(n)`
   `O(n^2)`
   `O(n * \log(n))`
   `O(\log(n))`

9. Kolikrát se zavolá funkce foo ()? for (i = 0; i < 2 * n; i++) if (i % 2 == 2) for (j = 0; j < 2 * n; j++) foo (); else for (j = n; j > 0; j /= 2) foo ();

   `O(\log (n))`
   `O(n*\log (n))`
   `O(\log(\log (n)))`
   `O(\log (n)*\log(n))`

10. Kolikrát se zavolá funkce foo ()? for (i = n; i != 0; i /= -2) for (j = 0; j < i * i; j++) foo ();

    `O(2^n)`
    `O(n^2)`
    `O(\log(n))`
    `O(n^3)`

11. Kolikrát se zavolá funkce foo ()? for (i = 1; i < 2 * n; i++) { if (i % 3 == 1) for (j = i; j < 2 * n; j++) foo (); else for (j = 0; j < i; j++) foo (); }

    `O(n!)`
    `O(n^2)`
    `O(n * \log(n))`
    `O(0)`

12. Kolikrát se zavolá funkce foo ()? for (i = n , j = (int)sqrt(n); i > 4;) { foo (); i /= j; j = (int)sqrt(i); }

    `O(\log(\log(n)))`
    `O(n*\log(\log(n)))`
    `O(\log(n))`
    `O(n*\log(n))`

13. Kolikrát se zavolá funkce foo ()? for (i = 1; i < n; i *= 2) for (j = 0; j < i; j++) for (k = n; k > 0; k /= 4) foo ();

    `O(\log (n))`
    `O(n * \log (n))`
    `O(\log (\log (n)))`
    `O(n^3)`

14. Kolikrát se zavolá funkce foo ()? for (i = 0; i < n; i++) { if (i % 2 == 0) for (j = -i; j < i; j += 2) foo(); else for (j = -i; j < i; j += 4) foo(); }

    `O(\log (n))`
    `O(n^2)`
    `O(n^3)`
    `O(n*\log(n))`