Dana jest następujący algorytm F(n) dla n ∈ N,n > 0:
F(n)
jeżeli n = 1, zwróć 1 i zakończ
w przeciwnym razie zwróć F(n div 2) + 1
55.1.
Złożoność tego algorytmu jest
| 1. | wykładnicza. | P | F |
|---|---|---|---|
| 2. | logarytmiczna. | P | F |
| 3. | liniowa. | P | F |
| 4. | kwadratowa. | P | F |
55.2.
Dla tego algorytmu zachodzi
| 1. | F(8) = 3. | P | F |
|---|---|---|---|
| 2. | F(12) = 4. | P | F |
| 3. | F(1) = 0 lub F(9) = 4. | P | F |
| 4. | F(1) = 1 oraz F(9) = 3. | P | F |
Poprawna odpowiedź
55.1. FPFF
55.2. FPPF