# Informatyka — zadanie 1.2

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

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

## Treść

Kontekst - patrz zadanie 1.1 (algorytm znajdowania pierwszej parzystej liczby w tablicy A).

Podaj, jaką złożoność czasową - kwadratową, liniową, logarytmiczną lub inną (napisz jaką) - ma Twój algorytm.

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

## Poprawna odpowiedź

**Złożoność czasowa: logarytmiczna - O(log n)**

(odpowiedź zgodna z algorytmem z zadania 1.1 - wyszukiwanie binarne)

## Sposób 1 - analiza pętli wyszukiwania binarnego

Kluczowe pytanie: **ile razy wykonuje się pętla `dopóki p < k`?**

- W każdej iteracji środek `s = (p+k) div 2` dzieli przedział `[p, k]` na dwie połowy.
- Wybierając jedną z połówek (w zależności od warunku A[s] mod 2), długość przedziału kurczy się **co najmniej dwukrotnie** w każdej iteracji.

**Formalnie:** jeśli na początku przedział ma długość n, to po k iteracjach ma długość co najwyżej n/2^k. Pętla kończy się gdy długość = 1, czyli n/2^k ≤ 1, skąd k ≥ log₂(n).

**Liczba iteracji = ⌈log₂(n)⌉ = O(log n).**

## Sposób 2 - alternatywne odpowiedzi w zależności od rozwiązania

- Jeśli w zadaniu 1.1 napisałeś **wyszukiwanie liniowe** (`for i := 1 to n do `) → złożoność **liniowa O(n)** (i tylko 3 pkt w 1.1).
- Jeśli wyszukiwanie binarne → **logarytmiczna O(log n)** (5 pkt w 1.1).
- Inne nietypowe rozwiązania:
- skok co `sqrt(n)` (jump search) → O(√n).
- rekurencyjne dzielenie połowiczne → O(log n) (równoważne binary search).

## Reference informatyczny - klasy złożoności

> Reference - Złożoność asymptotyczna:
> - **O(1)** - stała (np. dostęp do elementu tablicy).
> - **O(log n)** - logarytmiczna (binarka, wysokość zbalansowanego BST).
> - **O(n)** - liniowa (przegląd tablicy, sumowanie).
> - **O(n log n)** - quasi-liniowa (mergesort, heapsort, quicksort średni).
> - **O(n²)** - kwadratowa (bubble, insertion, selection sort).
> - **O(2ⁿ)** - wykładnicza (rekurencyjny Fibonacci bez memoizacji).
>
> Reguły uproszczeń:
> - Stałe się pomija: `5n + 100` → `O(n)`.
> - Suma → bierzemy największy człon: `O(n²) + O(n)` → `O(n²)`.
> - Iloczyn pętli zagnieżdżonych → mnoży się: `O(n)·O(log n)` → `O(n log n)`.

## Schemat oceniania CKE

> Klucz CKE (zadanie 1.2, max 1 pkt):
> - **1 pkt** - poprawna odpowiedź zgodna z algorytmem z 1.1
> - **0 pkt** - błędna lub brak

**Akceptowane:** `O(log n)`, `logarytmiczna`, `log(n)`, `log₂(n)` - wszystkie równoważne.
**Dla rozwiązania liniowego z 1.1:** `O(n)`, `liniowa`.

## Typowe pułapki

- **Pomylenie z poziomem pętli** - jedna pętla nie oznacza automatycznie O(n). Trzeba przeanalizować, **o ile** kurczy się przestrzeń w każdej iteracji.
- **Niezgodność odpowiedzi z algorytmem 1.1** - jeśli w 1.1 napisałeś binarkę, ale w 1.2 piszesz "liniowa" - zero punktów.
- **Mylenie log₂(n) z log₁₀(n)** - w informatyce logarytm domyślnie o podstawie 2 (lub e - nie ma znaczenia dla notacji O).
- **Pisanie tylko `O(log)` bez `n`** - to formalnie niepoprawne.

## Złożoność obliczeniowa

Algorytm wyszukiwania binarnego:
- **Czas: O(log n)** - pętla wykonuje co najwyżej ⌈log₂ n⌉ iteracji, każda w czasie O(1).
- **Pamięć: O(1)** - stała liczba zmiennych pomocniczych.

## Linki

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

## Podobne zadania

- [Zadanie 3](https://matura.lol/question/informatyka-2007-maj-matura-rozszerzona/zad/3) — Zadanie 3. (11 pkt) W tabeli podany jest algorytm, który pozwala obliczyć wartość pewnej sumy dla danej dodatniej liczby całkowitej n. 3.1. Podaj, jaką wartość 
- [Zadanie 3](https://matura.lol/question/informatyka-2015-przykladowy-arkusz-cke-rozszerzona/zad/3) — Zadanie 3. (0-9) Progi i schody W ciągu liczb naturalnych, parę sąsiednich liczb nazywamy progiem, jeśli następna liczba jest mniejsza od poprzedniej. W ciągu l
- [Zadanie 2.2](https://matura.lol/question/informatyka-2017-maj-matura-stara-podstawowa/zad/2.2) — Zadanie 2.2 (0-6) Zapisz algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku programowania) sprawdzający, czy dana liczba należy do pary 
- [Zadanie 2](https://matura.lol/question/informatyka-2015-przykladowy-arkusz-cke-rozszerzona/zad/2) — Zadanie 2. (0-6) Całkowity pierwiastek kwadratowy Niech będzie dodatnią liczbą całkowitą. Całkowitym pierwiastkiem kwadratowym z liczby ݊ nazywamy dodatnią licz

_Ostatnia aktualizacja danych: 2026-10-03_