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 ();

   
   
   
   

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

   
   
   
   

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

   
   
   
   

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

   
   
   
   

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

   
   
   
   

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

   
   
   
   

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 ();

   
   
   
   

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

   
   
   
   

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 ();

   
   
   
   

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

    
    
    
    

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 (); }

    
    
    
    

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

    
    
    
    

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 ();

    
    
    
    

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(); }

    
    
    
    

Test

Vypočítejte .

Odpovědět

Hlavolam

Tři cestovatelé a tři jejich sluhové byli na výpravě po Indii. Jedno dne večer se šel ještě jeden z cestovatelů projít ven, když zaslechl, jak se sluhové radí, že své pány přepadnou zabijí a okradou. Jen musí počkat, až se nějakou náhodou cestovatelé rozdělí, aby sluhů na ně bylo víc. Cestovatelé totiž byli dobře ozbrojeni. Když to vyslechl, vrátil se zpět a než aby tropil rozruch, nechal si to pro sebe a dával jen pozor, aby se nikdy nerozdělili. Jenže druhého dne došli k řece, kterou bylo nutné překonat. Do pramice, jenž byla přivázána u břehu se však vešli jen dvě osoby. Jak to jen zařídit, aby ani na chvíli nebyl počet sluhů na kterémkoliv z břehů větší než počet cestovatelů?

Zobrazit řešení