# Informatyka — zadanie 1.3

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2018-05/zad/1.3
> Wersja Markdown strony zadania (dla asystentów AI). Przy cytowaniu podaj matura.lol i link powyżej.

- arkusz: Informatyka · Matura · maj 2018 (rozszerzona)
- rok: 2018
- poziom: rozszerzona
- typ: closed
- punkty: 1
- działy: Programowanie i algorytmika, algorytmy

## Treść

Zadanie 1.3. (0-1)
Dokończ zdanie. Wybierz i zaznacz właściwą odpowiedź spośród podanych.
Dla każdej liczby całkowitej n > 1 instrukcja oznaczona w algorytmie symbolem (*)
wykona się
A. mniej niż 2·݈݋݃
ଶ݊ razy.
B. więcej niż n/2, ale mniej niż n razy.
C. więcej niż n+1, ale mniej niż 2n razy.
D. więcej niż n2 razy.
Wypełnia
egzaminator
Nr zadania
1.1.
1.2.
1.3.
Maks. liczba pkt.
3
2
1
Uzyskana liczba pkt.
MIN_1R

## Rozwiązanie — maturazai.pl (AI)

## Poprawna odpowiedź

**A** - mniej niż 2·log₂n razy.

## Sposób 1 - analiza algorytmu jako wyszukiwanie binarne

Algorytm z zadania 1.1 to **wyszukiwanie binarne** (binary search). Instrukcja (*) wykonuje się w każdej iteracji pętli `while p < q`.

**Kluczowa obserwacja:** W każdej iteracji długość przedziału `[p, q]` zmniejsza się co najmniej o połowę:
- Jeśli `s³ < n`: `p := s+1`, więc nowy przedział = `[s+1, q]`, długość ≤ q - s ≤ (q-p)/2.
- Jeśli `s³ ≥ n`: `q := s`, więc nowy przedział = `[p, s]`, długość = s - p ≤ (q-p)/2.

Początkowa długość przedziału = n - 1 ≈ n. Liczba iteracji potrzebnych do zmniejszenia z n do 1: **log₂(n)** iteracji.

## Sposób 2 - empirycznie

**Z symulacji w 1.1:**
- n = 28: 5 iteracji. log₂(28) ≈ 4.81. 2·log₂(28) ≈ 9.6. **5 < 9.6** ✓
- n = 64: 6 iteracji. log₂(64) = 6. 2·log₂(64) = 12. **6 < 12** ✓
- n = 80: 6 iteracji. log₂(80) ≈ 6.32. 2·log₂(80) ≈ 12.6. **6 < 12.6** ✓

Liczba iteracji jest **bliska log₂(n)**, więc na pewno mniejsza niż 2·log₂(n). Odpowiedź A.

## Sposób 3 - eliminacja błędnych opcji

### Opcja B: więcej niż n/2, mniej niż n razy
Dla n = 28: n/2 = 14, n = 28. Liczba iteracji = 5. 5 NIE jest > 14 → **B błędna**.

### Opcja C: więcej niż n+1, mniej niż 2n razy
Dla n = 28: n+1 = 29. Liczba iteracji = 5. 5 NIE jest > 29 → **C błędna**.

### Opcja D: więcej niż n² razy
Dla n = 28: n² = 784. Liczba iteracji = 5. 5 NIE jest > 784 → **D błędna**.

### Opcja A: mniej niż 2·log₂n razy
Dla n = 28: 2·log₂(28) ≈ 9.6. Iteracji 5 < 9.6 → **A poprawna** ✓.

## Reference informatyczny - złożoność wyszukiwania binarnego

> Reference - Wyszukiwanie binarne:
> - **Klasyczna złożoność**: O(log n).
> - **Dokładna liczba iteracji**: ⌈log₂(n)⌉ + O(1).
> - Każda iteracja zmniejsza długość przedziału co najmniej o połowę.
> - Dla n = 1024: ~10 iteracji. Dla n = 10⁶: ~20 iteracji.
>
> Reference - Klasy złożoności:
> | Klasa | Notacja | Przykład |
> |-------|---------|----------|
> | logarytmiczna | O(log n) | binary search, drzewo BST |
> | liniowa | O(n) | wyszukiwanie liniowe |
> | n log n | O(n log n) | mergesort, heapsort |
> | kwadratowa | O(n²) | bubble sort, naiwne porównanie par |
> | wykładnicza | O(2ⁿ) | brute-force kombinacji |
>
> Reference - Konwersja log:
> - log₂(n) = ln(n) / ln(2) = log₁₀(n) / log₁₀(2) ≈ log₁₀(n) · 3.32
> - log₂(1000) ≈ 10
> - log₂(10⁶) ≈ 20

## Schemat oceniania CKE

> Klucz CKE (zadanie 1.3, max 1 pkt):
> - **1 pkt** - odpowiedź **A**
> - **0 pkt** - błędna lub brak

## Typowe pułapki

- **Pomylenie z O(n)** - naiwna analiza "pętla się powtarza" sugeruje O(n), ale dzięki halving to O(log n).
- **Niezrozumienie struktury binary search** - jeśli ktoś nie widzi, że to wyszukiwanie binarne, może pomyśleć, że (*) wykonuje się n razy (B).
- **Mylenie 2·log₂n z log₂n²** - log₂(n²) = 2·log₂(n), więc obie formy są równoważne.
- **Pomylenie podstawy logarytmu** - log₂ (binarny) vs log₁₀ (dziesiętny). Różnica stała, ale w wartości liczbowej ważne.

## Złożoność obliczeniowa

- Liczba iteracji pętli `while`: O(log n).
- Instrukcja (*) wykonuje się raz na iterację: **O(log n)** razy.
- Każda iteracja: stały koszt (mnożenie + porównanie + przypisanie).
- **Łączna złożoność algorytmu: O(log n)** czas, O(1) pamięć.

## Odpowiedź

**Odpowiedź:** A

_Rozwiązanie AI z maturazai.pl, weryfikowane z kluczem CKE — źródło nieoficjalne._

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2018-05/zad/1.3)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2018-05%2Fzad%2F1.3)

## Podobne zadania

- [Zadanie 6.4](https://matura.lol/question/informatyka-2018-maj-matura-stara-podstawowa-2/zad/6.4) — Zadanie 6.4. (0-4) Makulatura przynoszona przez młodzież jest przechowywana w magazynie, a w każdy wtorek wieczorem przyjeżdża samochód ciężarowy po jej odbiór.
- [Zadanie 1.1](https://matura.lol/question/informatyka-2024-maj-matura-rozszerzona/zad/1.1) — Zadanie 1.1. (0-2) Podaj wynik działania algorytmu dla plansz podanych na rysunkach poniżej, gdzie n to liczba wierszy, a m to liczba kolumn danej planszy. a) n
- [Zadanie 1.3](https://matura.lol/question/informatyka-2020-czerwiec-matura-stara-rozszerzona/zad/1.3) — Zadanie 1.3. (2 pkt) Łączna liczba porównań w wierszach oznaczonych (*), wykonywanych w podanym algorytmie, jest równa (podkreśl właściwą odpowiedź) A. 𝑛 B. 2𝑛 
- [Zadanie 1.3](https://matura.lol/question/informatyka-2018-maj-matura-rozszerzona/zad/1.3) — Zadanie 1.3. (0-1) Dokończ zdanie. Wybierz i zaznacz właściwą odpowiedź spośród podanych. Dla każdej liczby całkowitej n > 1 instrukcja oznaczona w algorytmie s

_Ostatnia aktualizacja danych: 2026-10-03_