{"id":"informatyka-2019-maj-matura-rozszerzona/zad/1.2","paper_id":"informatyka-2019-maj-matura-rozszerzona","number":"1.2","points":1,"ptype":"open","subject":"informatyka","category":"matura","year":2019,"month":"maj","level":"rozszerzona","text":"Zadanie 1.2. (0-1)\nPodaj, jaką złożoność czasową - kwadratową, liniową, logarytmiczną lub inną (napisz jaką) -\nma Twój algorytm.\nWypełnia\negzaminator\nNr zadania\n1.1.\n1.2.\nMaks. liczba pkt.\n5\n1\nUzyskana liczba pkt.\nMIN_1R","answer":null,"answer_text":"Zadanie 1.2. (0-1)\nWymagania ogólne\nWymagania szczegółowe\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji […]\nz zastosowaniem podejścia algorytmicznego.\n5. Rozwiązywanie problemów\ni podejmowanie decyzji […], stosowanie\npodejścia algorytmicznego.\nZdający:\n4) dobiera efektywny algorytm do\nrozwiązania sytuacji problemowej i zapisuje\ngo w wybranej notacji;\n5) posługuje się podstawowymi technikami\nalgorytmicznymi;\n16) opisuje własności algorytmów na\npodstawie ich analizy;\n17) ocenia zgodność algorytmu ze\nspecyfikacją problemu;\n18) oblicza liczbę operacji wykonywanych\nprzez algorytm;\n20) bada efektywność komputerowych\nrozwiązań problemów.\nSchemat punktowania\n1 p. - za poprawną odpowiedź.\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nPoprawna odpowiedź\nNp. dla wyszukiwania binarnego: log(n) lub logarytmiczna, dla wyszukiwania liniowego -\nzłożoność liniowa.","solution":"## Poprawna odpowiedź\n\n**Złożoność czasowa: logarytmiczna - O(log n)**\n\n(odpowiedź zgodna z algorytmem z zadania 1.1 - wyszukiwanie binarne)\n\n## Sposób 1 - analiza pętli wyszukiwania binarnego\n\nKluczowe pytanie: **ile razy wykonuje się pętla `dopóki p < k`?**\n\n- W każdej iteracji środek `s = (p+k) div 2` dzieli przedział `[p, k]` na dwie połowy.\n- 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.\n\n**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).\n\n**Liczba iteracji = ⌈log₂(n)⌉ = O(log n).**\n\n## Sposób 2 - alternatywne odpowiedzi w zależności od rozwiązania\n\n- 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).\n- Jeśli wyszukiwanie binarne → **logarytmiczna O(log n)** (5 pkt w 1.1).\n- Inne nietypowe rozwiązania:\n- skok co `sqrt(n)` (jump search) → O(√n).\n- rekurencyjne dzielenie połowiczne → O(log n) (równoważne binary search).\n\n## Reference informatyczny - klasy złożoności\n\n> Reference - Złożoność asymptotyczna:\n> - **O(1)** - stała (np. dostęp do elementu tablicy).\n> - **O(log n)** - logarytmiczna (binarka, wysokość zbalansowanego BST).\n> - **O(n)** - liniowa (przegląd tablicy, sumowanie).\n> - **O(n log n)** - quasi-liniowa (mergesort, heapsort, quicksort średni).\n> - **O(n²)** - kwadratowa (bubble, insertion, selection sort).\n> - **O(2ⁿ)** - wykładnicza (rekurencyjny Fibonacci bez memoizacji).\n>\n> Reguły uproszczeń:\n> - Stałe się pomija: `5n + 100` → `O(n)`.\n> - Suma → bierzemy największy człon: `O(n²) + O(n)` → `O(n²)`.\n> - Iloczyn pętli zagnieżdżonych → mnoży się: `O(n)·O(log n)` → `O(n log n)`.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 1.2, max 1 pkt):\n> - **1 pkt** - poprawna odpowiedź zgodna z algorytmem z 1.1\n> - **0 pkt** - błędna lub brak\n\n**Akceptowane:** `O(log n)`, `logarytmiczna`, `log(n)`, `log₂(n)` - wszystkie równoważne.\n**Dla rozwiązania liniowego z 1.1:** `O(n)`, `liniowa`.\n\n## Typowe pułapki\n\n- **Pomylenie z poziomem pętli** - jedna pętla nie oznacza automatycznie O(n). Trzeba przeanalizować, **o ile** kurczy się przestrzeń w każdej iteracji.\n- **Niezgodność odpowiedzi z algorytmem 1.1** - jeśli w 1.1 napisałeś binarkę, ale w 1.2 piszesz \"liniowa\" - zero punktów.\n- **Mylenie log₂(n) z log₁₀(n)** - w informatyce logarytm domyślnie o podstawie 2 (lub e - nie ma znaczenia dla notacji O).\n- **Pisanie tylko `O(log)` bez `n`** - to formalnie niepoprawne.\n\n## Złożoność obliczeniowa\n\nAlgorytm wyszukiwania binarnego:\n- **Czas: O(log n)** - pętla wykonuje co najwyżej ⌈log₂ n⌉ iteracji, każda w czasie O(1).\n- **Pamięć: O(1)** - stała liczba zmiennych pomocniczych.","image":"img/informatyka-2019-maj-matura-rozszerzona/zad-1.2.webp","solution_image":null,"topics":null,"page_from":3,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2019 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1.2. (0-1)
Podaj, jaką złożoność czasową - kwadratową, liniową, logarytmiczną lub inną (napisz jaką) -
ma Twój algorytm.
Wypełnia
egzaminator
Nr zadania
1.1.
1.2.
Maks. liczba pkt.
5
1
Uzyskana liczba pkt.
MIN_1R

","answer_text_html":"

Zadanie 1.2. (0-1)
Wymagania ogólne
Wymagania szczegółowe
III. Rozwiązywanie problemów
i podejmowanie decyzji […]
z zastosowaniem podejścia algorytmicznego.

\n
  1. Rozwiązywanie problemów
\n

i podejmowanie decyzji […], stosowanie
podejścia algorytmicznego.
Zdający:

\n
  1. dobiera efektywny algorytm do
\n

rozwiązania sytuacji problemowej i zapisuje
go w wybranej notacji;

\n
  1. posługuje się podstawowymi technikami
\n

algorytmicznymi;

\n
  1. opisuje własności algorytmów na
\n

podstawie ich analizy;

\n
  1. ocenia zgodność algorytmu ze
\n

specyfikacją problemu;

\n
  1. oblicza liczbę operacji wykonywanych
\n

przez algorytm;

\n
  1. bada efektywność komputerowych
\n

rozwiązań problemów.
Schemat punktowania
1 p. - za poprawną odpowiedź.
0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Poprawna odpowiedź
Np. dla wyszukiwania binarnego: log(n) lub logarytmiczna, dla wyszukiwania liniowego -
złożoność liniowa.

","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"

Poprawna odpowiedź

\n

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

\n

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

\n

Sposób 1 - analiza pętli wyszukiwania binarnego

\n

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

\n\n

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).

\n

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

\n

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

\n\n

Reference informatyczny - klasy złożoności

\n
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).
\n

Schemat oceniania CKE

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

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

\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n

Algorytm wyszukiwania binarnego:

\n"}]}