Ile pytań do prawdy — logarytm binarny
🎯 Po co Ci to?
W tym dziale to samo pytanie wróciło już trzy razy w przebraniach: ile bitów na 366 dni (2.1)? ile pytań w zgadywance do 1000 (dział 1)? ile poziomów kwantyzacji na 16 bitach (2.5)? Za każdym razem odpowiedź brzmiała „taka potęga dwójki, żeby starczyło". Matematyka ma dla tej odpowiedzi jedno słowo — logarytm — i w informatyce spotkasz je częściej niż w jakiejkolwiek innej dziedzinie. Czas się zaprzyjaźnić, bo od działu 6 będzie liczyć koszty Twoich algorytmów.
✅ Czego się nauczysz
Po tej jednostce potrafisz:
- obliczać logarytm binarny dokładnie (dla potęg dwójki) i szacunkowo (dla pozostałych liczb);
- tłumaczyć zdania „ile bitów / ile połowień / ile poziomów drzewa" na język logarytmu;
- wyjaśnić, dlaczego algorytmy „logarytmiczne" niemal nie czują wzrostu danych.
🔁 Przypomnij sobie
Z 1.4: każde pytanie połowiące zmniejsza pulę kandydatów dwukrotnie; z 2.1: $n$ bitów rozróżnia $2^n$ możliwości. Logarytm to te dwa fakty przeczytane od tyłu.
📘 Wyjaśnienie
📐 DEFINICJA — logarytm binarny: $\log_2 n$ to wykładnik, do którego trzeba podnieść 2, żeby otrzymać $n$: $;\log_2 n = k \iff 2^k = n$.
Po ludzku: „ile razy trzeba podwoić 1, żeby dojść do $n$" — albo od drugiej strony: „ile razy trzeba przepołowić $n$, żeby zejść do 1". Czym NIE jest: nowym rodzajem działania do wykucia. To pytanie o wykładnik, które zadawałeś już wielokrotnie — teraz ma tylko krótszy zapis.
Dla potęg dwójki wynik odczytujesz wprost: $\log_2 8 = 3$, $\log_2 256 = 8$, $\log_2 1024 = 10$. Dla pozostałych liczb wystarczy nam szacowanie między sąsiednimi potęgami: $\log_2 1000$ leży między $\log_2 512 = 9$ a $\log_2 1024 = 10$, blisko górnej granicy — około $9{,}97$. W praktyce algorytmicznej i tak interesuje nas zaokrąglenie w górę: żeby rozróżnić 1000 możliwości, potrzeba 10 bitów/pytań (dziewięć to za mało: $2^9 = 512$).
Trzy zdania, które znaczą dokładnie to samo — ucz się przeskakiwać między nimi płynnie:
- „Na zapisanie $n$ różnych wartości potrzeba $\log_2 n$ bitów (w górę)."
- „Połowienie sprowadza $n$ kandydatów do jednego w $\log_2 n$ krokach."
- „Zrównoważone drzewo decyzji o $n$ liściach ma głębokość $\log_2 n$."
Dlaczego to takie potężne? Spójrz, jak leniwie rośnie logarytm: tysiąc → 10, milion → 20, miliard → 30, wszystkie atomy obserwowalnego wszechświata (~$10^{80}$) → około 266. Podwojenie danych dokłada jeden krok. Algorytm o koszcie $\log_2 n$ praktycznie nie zauważa, że dane urosły — dlatego wyszukiwanie w miliardowej bazie trwa mgnienie, a hasło o 30 znakach jest astronomicznie mocniejsze niż o 15. Odwrotna strona medalu: wykładniczy wzrost ($2^n$) jest równie bezlitośnie szybki, jak logarytm wolny — to dwie strony tej samej monety.
💭 Pomyśl: Papier da się złożyć na pół najwyżej 7–8 razy, ale gdyby się dało — ile złożeń kartki grubości 0,1 mm zbudowałoby stos sięgający Księżyca (384 000 km)?
Sprawdź odpowiedź
Szukamy $k$ z warunkiem $0{,}1\text{ mm} \cdot 2^k \ge 3{,}84 \cdot 10^{11}$ mm, czyli $2^k \ge 3{,}84 \cdot 10^{12}$. Ponieważ $2^{40} \approx 1{,}1 \cdot 10^{12}$, a $2^{42} \approx 4{,}4 \cdot 10^{12}$ — wystarczą 42 złożenia. Czterdzieści dwa podwojenia od dziesiątej części milimetra do Księżyca; dokładnie ta sama siła, która sprawia, że 42 pytania połowiące przeszukałyby cztery biliony rekordów.
🧮 Prześledź
Uzupełnij tabelkę (bez kalkulatora — tylko potęgi dwójki i szacowanie):
| $n$ | $\log_2 n$ dokładnie lub „między … a …" | bitów potrzeba (w górę) |
|---|---|---|
| 64 | ? | ? |
| 100 | ? | ? |
| 4096 | ? | ? |
| 50 000 | ? | ? |
Sprawdź odpowiedź
64: dokładnie 6 → 6 bitów. 100: między $\log_2 64 = 6$ a $\log_2 128 = 7$ → 7 bitów. 4096: dokładnie 12 → 12 bitów. 50 000: między $\log_2 32768 = 15$ a $\log_2 65536 = 16$ → 16 bitów. (Dlatego właśnie 16-bitowy licznik z zadania w 2.3 kończył się na 65 535.)
🌍 Powiązania
Logarytm — tyle że dziesiętny — spotkałeś już w szkole w skali pH i skali Richtera, a jego własności ćwiczyłeś na matematyce. Informatyka dorzuca swoją podstawę (2, bo bity) i swoją intuicję (liczba połowień). Gdy na matematyce rozszerzonej dojdziesz do wykresów logarytmu — zobaczysz dokładnie tę „płaską" krzywą, którą narysowaliśmy w jednostce 1.5, porównując koszty algorytmów.
🛠️ Teraz Ty
Bez komputera: gra w 20 pytań pozwala zadać 20 pytań tak/nie — ilu różnych „rzeczy" teoretycznie pozwala to rozróżnić i co to mówi o sile dobrze zadawanych pytań? Z komputerem: import math; math.log2(1000) — sprawdź swoje szacunki z tabelki.
📐 Definicje tej lekcji
- Logarytm binarny ($\log_2 n$) — wykładnik potęgi dwójki dającej $n$; liczba podwojeń od 1 do $n$ i połowień z $n$ do 1.
📌 Najważniejsze w pigułce
- $\log_2$ odpowiada na pytania: ile bitów, ile pytań, ile połowień, jak głębokie drzewo.
- Rośnie leniwie: milion → 20, miliard → 30; podwojenie danych = +1 krok.
- Logarytm i wykładnik to jedna moneta: dlatego połowienie jest błogosławieństwem, a wybuch wykładniczy — przekleństwem.
🎒 Zadania
- Turniej szachowy „przegrywasz — odpadasz" zaczyna 128 osób. Ile rund trzeba rozegrać, by wyłonić mistrza? A gdyby zgłosiło się 200 osób?
Wskazówka i odpowiedź
Każda runda połowi liczbę graczy: $\log_2 128 = 7$ rund. Dla 200 osób: $2^7 = 128 < 200 \le 256 = 2^8$ → 8 rund (część pierwszej rundy to „wolne losy"). Drabinka turniejowa to drzewo z ryciny — tylko liście nazywają się zawodnikami.
- Hasło A ma 8 znaków, hasło B — 16 znaków (ten sam alfabet, powiedzmy 64 możliwe znaki na pozycję). Ile bitów „siły" ma każde i co to znaczy dla łamiącego?
Wskazówka i odpowiedź
Jedna pozycja z 64 możliwości niesie $\log_2 64 = 6$ bitów. A: $8 \times 6 = 48$ bitów, B: $16 \times 6 = 96$ bitów. Różnica 48 bitów oznacza $2^{48} \approx 2{,}8 \cdot 10^{14}$ razy więcej kombinacji do sprawdzenia — podwojenie długości hasła nie podwaja trudności łamania, tylko mnoży ją przez setki bilionów. Wnioski praktyczne wyciągniesz w dziale o bezpieczeństwie.
- Biblioteka ma katalog 2 000 000 pozycji, posortowany alfabetycznie. Bibliotekarka twierdzi, że znajdzie każdą pozycję, sprawdzając najwyżej 21 miejsc. Blefuje?
Wskazówka i odpowiedź
Nie blefuje: szuka połowieniem. $2^{21} = 2,097,152 \ge 2,000,000$, więc 21 „zajrzeń" (środek, potem środek właściwej połówki, …) zawsze wystarczy. W dziale 6 zaprogramujesz tę strategię pod nazwą wyszukiwania binarnego — i udowodnisz, że 20 zajrzeń mogłoby czasem nie starczyć.
🔍 Sprawdź, czy umiesz
- Podać z pamięci $\log_2$ dla 2, 8, 32, 256, 1024 — i oszacować dla 500.
- Przetłumaczyć „potrzeba $k$ bitów" na zdanie o pytaniach tak/nie i z powrotem.
- Wyjaśnić jednym zdaniem, dlaczego algorytmy logarytmiczne skalują się niemal za darmo.