ZAWODNIK

Algorytmy i struktury danych na egzaminie INF.04

INF.04 · teoria
autor: redakcja · 24.08.2026
Algorytmy i struktury danych w kwalifikacji INF.04: najważniejsze zasady, przykłady i 51 powiązanych pytań w banku.

[ INF.04: PYTANIA Z TEGO DZIAŁU ]

Przejrzyj pytania: algorytmyĆwicz dział: algorytmy
Ana­li­za al­go­ryt­mu od­po­wia­da na dwa py­ta­nia: czy daje po­praw­ny wynik i jak rośnie koszt wy­ko­na­nia wraz z roz­mia­rem danych. W INF.04 trzeba śle­dzić pseu­do­kod, roz­po­zna­wać al­go­ryt­my wy­szu­ki­wa­nia i sor­to­wa­nia oraz świa­do­mie od­róż­niać przy­pa­dek naj­lep­szy, średni i naj­gor­szy.

Co opi­su­je no­ta­cja zło­żo­no­ści

Dla wej­ścia o roz­mia­rze n liczy się do­mi­nu­ją­cą liczbę ope­ra­cji. Stałe i wol­niej ro­sną­ce skład­ni­ki pomija się przy opisie rzędu wzro­stu: 3n + 7 za­pi­su­je się jako O(n), a dwie za­gnież­dżo­ne pętle po n ele­men­tów zwykle pro­wa­dzą do O(n^2). Zło­żo­ność cza­so­wa nie jest czasem w se­kun­dach, tylko spo­so­bem po­rów­na­nia wzro­stu kosztu.
Uwzględ­niaj też pamięć: sor­to­wa­nie przez sca­la­nie działa w O(n log n), ale typowa im­ple­men­ta­cja po­trze­bu­je do­dat­ko­wej ta­bli­cy O(n). Al­go­rytm może być szyb­szy kosz­tem pa­mię­ci. O(1) pa­mię­ci do­dat­ko­wej ozna­cza stałą liczbę zmien­nych nie­za­leż­ną od wiel­ko­ści danych.

Wy­szu­ki­wa­nie li­nio­we i bi­nar­ne

Al­go­rytm
Wa­ru­nek
Naj­lep­szy
Średni i naj­gor­szy
li­nio­we
żaden
O(1) (ele­ment pierw­szy)
O(n)
bi­nar­ne
dane po­sor­to­wa­ne
O(1) (tra­fie­nie w środek)
O(log n)
Koszt wcze­śniej­sze­go sor­to­wa­nia może spra­wić, że po­je­dyn­cze wy­szu­ka­nie w nie­po­sor­to­wa­nej małej ta­bli­cy lepiej wy­ko­nać li­nio­wo.

Sor­to­wa­nia różnią się nie tylko nazwą

Sor­to­wa­nie
Naj­lep­szy
Średni
Naj­gor­szy
Uwagi
bą­bel­ko­we z prze­rwa­niem
O(n)
O(n^2)
O(n^2)
prze­rwa­nie przy braku zamian
przez wybór
O(n^2)
O(n^2)
O(n^2)
tyle samo po­rów­nań nawet dla upo­rząd­ko­wa­nych
przez wsta­wia­nie
O(n)
O(n^2)
O(n^2)
szyb­kie dla prawie po­sor­to­wa­nych
przez sca­la­nie
O(n log n)
O(n log n)
O(n log n)
pamięć po­moc­ni­cza O(n)
szyb­kie
O(n log n)
O(n log n)
O(n^2)
naj­gor­szy przy skraj­nie nie­rów­nych po­dzia­łach
Sta­bil­ność ozna­cza za­cho­wa­nie ko­lej­no­ści ele­men­tów o rów­nych klu­czach: ma zna­cze­nie przy ko­lej­nym sor­to­wa­niu re­kor­dów wcze­śniej upo­rząd­ko­wa­nych po na­zwi­sku. Prze­bieg każ­de­go z tych al­go­ryt­mów obej­rzysz krok po kroku w wi­zu­ali­za­cji al­go­ryt­mów sor­to­wa­nia.

Dobór struk­tu­ry danych do ope­ra­cji

Struk­tu­ra
Mocna strona
Słaba strona
ta­bli­ca
dostęp po in­dek­sie O(1)
wsta­wie­nie na po­cząt­ku prze­su­wa ele­men­ty
lista wią­za­na
wsta­wie­nie przy znanym węźle
doj­ście do ele­men­tu k jest se­kwen­cyj­ne
stos
LIFO: ostat­ni wszedł, pierw­szy wy­szedł
tylko wierz­cho­łek
ko­lej­ka
FIFO: pierw­szy wszedł, pierw­szy wy­szedł
tylko po­czą­tek i koniec
ta­bli­ca mie­sza­ją­ca
ocze­ki­wa­ny dostęp O(1)
ko­li­zje; w skraj­nym przy­pad­ku O(n)
zrów­no­wa­żo­ne drzewo BST
odczyt, do­da­nie, usu­nię­cie O(log n)
bar­dziej zło­żo­na im­ple­men­ta­cja
Wybór zależy od tego, czy waż­niej­sze są wy­szu­ki­wa­nie, ko­lej­ność, częste wsta­wie­nia czy zu­ży­cie pa­mię­ci.

Jak ana­li­zo­wać pseu­do­kod

  • 1.
    Utwórz tabelę war­to­ści zmien­nych i wy­ko­nuj in­struk­cje do­kład­nie w po­da­nej ko­lej­no­ści.
  • 2.
    Przy pętli zapisz war­to­ści gra­nicz­ne i sprawdź, czy koniec prze­dzia­łu należy do za­kre­su.
  • 3.
    Przy re­ku­ren­cji naj­pierw znajdź wa­ru­nek koń­czą­cy, potem roz­pisz kilka wy­wo­łań do mo­men­tu po­wro­tu.
  • 4.
    Zło­żo­ność oce­niaj po usta­le­niu liczby po­wtó­rzeń: ko­lej­ne pętle sumują koszty, pętla w pętli zwykle je mnoży.
  • 5.
    Pętla zmniej­sza­ją­ca zakres o jeden daje zwykle O(n), a dzie­lą­ca go przez dwa O(log n); wy­jąt­ki wy­ni­ka­ją z pracy wy­ko­ny­wa­nej we­wnątrz.
Za­da­nia z pseu­do­ko­dem znaj­dziesz w ar­ku­szach INF.04, a śle­dze­nie kodu obiek­to­we­go opi­su­je ar­ty­kuł o pro­gra­mo­wa­niu obiek­to­wym.

[ INF.04: INNE ARTYKUŁY ]

Hub INF.04Zakres materiałuAplikacje desktopowe, mobilne i webowe na egzaminie INF.04Frameworki i biblioteki na egzaminie INF.04Programowanie obiektowe na egzaminie INF.04Testowanie oprogramowania na egzaminie INF.04Teoria INF.04
ZAWODNIK
egzamin zawodowy INF.02 · INF.03 · INF.04
Serwer Discord›
Egzaminy zawodowe IT/Matury/Studia
@yastor
Polityka prywatnościRegulaminKontakt
© 2026 Zawodnik · by Yastor
Arkusze i zasady oceniania pochodzą z CKE. Serwis nie jest powiązany z Centralną Komisją Egzaminacyjną.