Który przepis lepszy?

🎯 Po co Ci to?

Dwa programy robią to samo. Pierwszy odpowiada natychmiast, drugi mieli dane trzy godziny. Obydwa są poprawne — a jednak nikt nie ma wątpliwości, który jest lepszy. Poprawność to za mało: algorytmy mają jeszcze cenę, płaconą w liczbie kroków. Dziś nauczysz się tę cenę wyznaczać — na razie bez wielkiej teorii, za to z ołówkiem w ręku. To umiejętność, która odróżnia ludzi piszących programy od ludzi rozumiejących, co napisali.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • policzyć (lub oszacować), ile kroków wykonuje algorytm dla danych rozmiaru $n$;
  • porównać dwa poprawne algorytmy i uzasadnić, który jest szybszy — i czy różnica ma znaczenie;
  • przeanalizować gotowy algorytm, którego sam nie pisałeś.

🔁 Przypomnij sobie

Z jednostki 1.4: strategia „po kolei" potrzebowała 100 pytań, strategia połowienia — 7. Dziś zrobimy z tej obserwacji metodę.

📘 Wyjaśnienie

Porównajmy dwa algorytmy na tym samym problemie. Dane: liczba naturalna $n$. Wynik: suma $1 + 2 + \dots + n$.

Algorytm A — zsumuj po kolei:

wczytaj n
suma ← 0
dla i od 1 do n
    suma ← suma + i
wypisz suma

Algorytm B — wzór:

wczytaj n
suma ← n · (n + 1) / 2
wypisz suma

Obydwa są poprawne (wzór z algorytmu B znasz z matematyki — to suma ciągu arytmetycznego). Ale policz kroki. Algorytm A wykonuje $n$ dodawań: dla $n$ = milion — milion operacji. Algorytm B wykonuje jedno mnożenie, jedno dodawanie i jedno dzielenie — trzy operacje, niezależnie od $n$. Dla $n$ = miliard: miliard kroków kontra trzy.

🕰️ Skąd to wiemy: anegdota mówi, że mały Carl Friedrich Gauss dostał w szkole za karę zsumowanie liczb od 1 do 100 — i odpowiedział po chwili: 5050. Zauważył, że pary (1+100), (2+99), (3+98)… dają po 101, a par jest 50: $50 \cdot 101 = 5050$. Nauczyciel liczył na pół godziny spokoju; dostał algorytm B. Morał: najlepsze przyspieszenia nie biorą się z szybszego liczenia, tylko z innego spojrzenia na problem.

Jak liczyć kroki, gdy nie ma wzoru? Zwykle interesuje nas nie dokładna liczba operacji, tylko jak rośnie z rozmiarem danych $n$:

  • Algorytm B: stała liczba kroków — rozmiar danych nie ma znaczenia.
  • Algorytm A: liczba kroków rośnie proporcjonalnie do $n$ — dwa razy większe dane, dwa razy dłuższa praca.
  • Zgadywanka „po kolei" z jednostki 1.4: proporcjonalnie do $n$.
  • Zgadywanka połowieniem: liczba kroków to liczba połowień — rośnie, ale absurdalnie wolno (milion → 20, miliard → 30).
n (rozmiar danych)liczba kroków50010005001000krok za krokiem (n kroków)połowienie (log₂ n kroków)1000≈10
Porównanie liczby kroków: przy wzroście n prosta „krok za krokiem" (proporcjonalnie do n) ucieka w górę, a krzywa połowienia pozostaje płaska — dla n = 1000 różnica to 1000 kroków wobec 10. · rys. własny

Ta różnica nie jest akademicka. Wyszukiwarka, która na każde zapytanie przegląda internet „po kolei", nie odpowiedziałaby za Twojego życia. Odpowiada w ułamku sekundy, bo jej struktury danych działają w rytmie połowienia. Kiedy w dziale 6 porównamy sortowania, a w rozszerzeniu poznasz notację, którą informatycy opisują tempo wzrostu — będziesz już czuł, o co toczy się gra.

Analiza cudzego algorytmu. Na maturze i w życiu częściej czytasz algorytmy, niż piszesz. Technika jest zawsze ta sama: (1) prześledź dla małych danych, (2) nazwij, co robi każda zmienna, (3) policz, ile razy wykona się najbardziej wewnętrzna operacja.

💭 Pomyśl: Ktoś proponuje algorytm C na tę samą sumę: „dla każdego $i$ od 1 do $n$: dla każdego $j$ od 1 do $i$: dodaj 1 do licznika". Wynik jest poprawny (licznik policzy $1+2+\dots+n$ jedynek). Ile mniej więcej kroków wykonuje dla $n = 1000$?

Sprawdź odpowiedź

Wewnętrzna operacja wykonuje się $1 + 2 + \dots + 1000 = 500,500$ razy — pół miliona kroków tam, gdzie algorytm A potrzebował tysiąca, a B trzech. Liczba kroków rośnie tu jak $n^2/2$, czyli kwadratowo: dziesięć razy większe dane, sto razy więcej pracy. Poprawny nie znaczy rozsądny.

⚠️ Uwaga, pułapka

„Szybszy algorytm" nie znaczy „krótszy zapis". Algorytm C z ćwiczenia wyżej jest krótki i elegancki — i katastrofalnie wolny. Odwrotnie też bywa: dłuższy kod bywa szybszy. Cenę algorytmu mierzy się liczbą wykonywanych operacji, nie liczbą linijek.

🛠️ Teraz Ty

Problem: sprawdź, czy liczba $k$ występuje na liście $n$ liczb. Zaproponuj algorytm dla listy nieuporządkowanej i osobno pomyśl: gdyby lista była posortowana rosnąco, jak wykorzystałbyś pomysł połowienia? Ile kroków (mniej więcej) kosztuje każda wersja dla $n = 1000$? Nie podglądaj działu 6 — wystarczy to, co już umiesz.

📐 Definicje tej lekcji

  • Koszt algorytmu — liczba operacji wykonywanych dla danych rozmiaru $n$; interesuje nas przede wszystkim tempo wzrostu tej liczby.
  • Wzrost liniowy / kwadratowy / logarytmiczny (nazwy robocze) — kroki rosną: proporcjonalnie do $n$ / jak $n^2$ / jak liczba połowień $n$.

📌 Najważniejsze w pigułce

  • Poprawność to warunek wstępny; algorytmy różnią się ceną liczoną w krokach.
  • Cenę ocenia się po tempie wzrostu: stała < połowienie < proporcjonalnie do $n$ < kwadratowo.
  • Największe przyspieszenia daje zmiana pomysłu (Gauss), nie szybszy komputer.

🎒 Zadania

  1. Dla $n = 10,000$ oszacuj liczbę kroków algorytmów A, B i C z tej jednostki.
Wskazówka i odpowiedź

A: około $10,000$ dodawań. B: trzy operacje. C: $1+2+\dots+10,000 = \frac{10,000 \cdot 10,001}{2} \approx 50$ milionów. Ten sam problem, trzy ceny różniące się o rzędy wielkości — i wszystkie trzy odpowiedzi „poprawne".

  1. Telefon wykonuje miliard prostych operacji na sekundę. Ile czasu zajmie mu algorytm o koszcie $n$, a ile o koszcie $n^2$, dla $n$ = milion?
Wskazówka i odpowiedź

Koszt $n$: $10^6$ operacji → jedna tysięczna sekundy. Koszt $n^2$: $10^{12}$ operacji → około 1000 sekund, czyli kwadrans z okładem. Ta sama maszyna, te same dane — różnica tylko w algorytmie. Teraz już wiesz, dlaczego informatycy kłócą się o algorytmy, a nie o gigaherce.

  1. Wróć do zadania „ile liczb parzystych na liście" (jednostka 1.2). Jak rośnie jego koszt z długością listy? Czy istnieje sprytniejszy algorytm w stylu Gaussa?
Wskazówka i odpowiedź

Koszt rośnie proporcjonalnie do $n$ — każdą liczbę trzeba obejrzeć raz. I tu niespodzianka: nie ma drogi na skróty. Skoro dowolna liczba na liście może zmienić wynik, algorytm, który jakiejś nie obejrzy, może się mylić. Wniosek: proporcjonalnie do $n$ to dolna granica dla tego problemu. Czasem „przyspieszyć się nie da" jest równie cenną wiedzą, jak sprytny wzór — oszczędza szukania czegoś, czego nie ma.

🔍 Sprawdź, czy umiesz

  • Policzyć koszt prostego algorytmu z pętlą dla danych rozmiaru $n$.
  • Wyjaśnić na przykładzie Gaussa, czym różni się przyspieszenie sprzętowe od algorytmicznego.
  • Rozstrzygnąć, który z dwóch poprawnych algorytmów wybrać — i uzasadnić.

Ucz się tej jednostki z asystentem