Logarytm binarny
gdzie x jest liczbą logarytmowaną (x > 0), podstawa logarytmu to 2
Czym jest logarytm binarny?
Logarytm binarny to logarytm o podstawie 2, oznaczany symbolem log₂ x, lb x lub lg x (w informatyce). Jest to fundamentalne narzędzie w informatyce, teorii informacji i analizie algorytmów. Podstawa 2 została wybrana ze względu na binarny system liczbowy, który jest podstawą działania komputerów.
Logarytm binarny odpowiada na pytanie: do jakiej potęgi należy podnieść 2, aby otrzymać daną liczbę? Na przykład, log₂ 8 = 3, ponieważ 2³ = 8. W kontekście informatycznym można to interpretować jako pytanie: ile bitów potrzeba do reprezentacji danej liczby? lub: ile razy można podzielić liczbę przez 2, zanim otrzymamy 1?
W informatyce logarytm binarny pojawia się wszędzie: w analizie złożoności algorytmów (np. O(log n) dla wyszukiwania binarnego), w strukturach danych (wysokość drzew binarnych), w teorii informacji (entropia, kompresja danych) oraz w obliczeniach związanych z pamięcią i adresowaniem. Jest to jeden z najważniejszych logarytmów w naukach komputerowych.
Elementy wzoru
Symbol logarytmu binarnego z wyraźnie zaznaczoną podstawą 2. Najczęstszy zapis w matematyce i informatyce teoretycznej.
Skrót od łacińskiego logarithmus binarius. Alternatywna notacja logarytmu binarnego, stosowana głównie w Europie.
Liczba logarytmowana (argument logarytmu). Musi być liczbą dodatnią (x > 0), ponieważ logarytm z liczby ujemnej lub zera nie jest określony w zbiorze liczb rzeczywistych.
Podstawa logarytmu binarnego. Wybrana ze względu na binarny system liczbowy używany w komputerach. Oznacza, że pytamy: 2 do jakiej potęgi równa się x?
Interpretacja i właściwości
Logarytm binarny log₂ x odpowiada na pytanie: do jakiej potęgi należy podnieść 2, aby otrzymać x? Jeśli log₂ x = y, to 2^y = x. Ta relacja sprawia, że logarytm binarny jest funkcją odwrotną do funkcji wykładniczej 2^x.
W informatyce logarytm binarny ma intuicyjną interpretację: log₂ n to liczba bitów potrzebnych do reprezentacji liczby n (zaokrąglona w górę). Na przykład, log₂ 8 = 3 oznacza, że potrzebujemy 3 bitów do zakodowania liczb od 0 do 7. Logarytm binarny określa również maksymalną głębokość zrównoważonego drzewa binarnego z n węzłami.
Logarytm binarny ma wszystkie standardowe właściwości logarytmów: log₂(ab) = log₂ a + log₂ b, log₂(a/b) = log₂ a - log₂ b, log₂(a^n) = n·log₂ a. Dodatkowo log₂ 1 = 0 (bo 2^0 = 1) oraz log₂ 2 = 1 (bo 2^1 = 2). Dla potęg dwójki obliczenia są szczególnie proste: log₂ 4 = 2, log₂ 8 = 3, log₂ 16 = 4, log₂ 32 = 5.
Wizualizacja
Poniższy wykres pokazuje funkcję logarytmu binarnego y = log₂ x (zielona) oraz funkcję wykładniczą y = 2^x (niebieska). Są to funkcje wzajemnie odwrotne, co widać po ich symetrii względem prostej y = x (czerwona przerywana).
Funkcja logarytmu binarnego
Funkcja wykładnicza o podstawie 2
Oś symetrii funkcji odwrotnych
Kiedy stosować logarytm binarny?
- Analiza złożoności algorytmów - O(log n) dla wyszukiwania binarnego, sortowania przez scalanie, operacji na drzewach
- Struktury danych - wysokość drzew binarnych, głębokość rekursji, liczba poziomów w hierarchii
- Teoria informacji - entropia, kompresja danych, kodowanie Huffmana, ilość informacji w bitach
- Reprezentacja liczb - obliczanie liczby bitów potrzebnych do zakodowania liczby, adresowanie pamięci
- Kryptografia - długość kluczy, bezpieczeństwo szyfrów, złożoność łamania haseł
- Grafika komputerowa - poziomy mipmapingu, drzewa BSP, octree'y
Przykłady obliczeniowe
Przykład 1: Podstawowe obliczenia
Zadanie: Oblicz log₂ 64.
Rozwiązanie:
Przedstawiamy 64 jako potęgę dwójki:
Odpowiedź: log₂ 64 = 6 (potrzeba 6 bitów do reprezentacji liczb 0-63)
Przykład 2: Liczba bitów
Zadanie: Ile bitów potrzeba, aby zakodować 1000 różnych wartości?
Rozwiązanie:
Obliczamy log₂ 1000 i zaokrąglamy w górę:
Sprawdzenie: 2⁹ = 512 (za mało), 2¹⁰ = 1024 (wystarczy)
Odpowiedź: Potrzeba 10 bitów.
Przykład 3: Złożoność algorytmu
Zadanie: Ile kroków wykona wyszukiwanie binarne w tablicy 1024 elementów w najgorszym przypadku?
Rozwiązanie:
Złożoność wyszukiwania binarnego to O(log₂ n):
W każdym kroku dzielimy tablicę na pół: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1
Odpowiedź: Maksymalnie 10 kroków (porównań).
Przykład 4: Wysokość drzewa binarnego
Zadanie: Jaka jest minimalna wysokość zrównoważonego drzewa binarnego z 100 węzłami?
Rozwiązanie:
Minimalna wysokość to ⌈log₂(n+1)⌉ - 1:
Odpowiedź: Minimalna wysokość wynosi 6.
Przykład 5: Rozwiązanie równania
Zadanie: Rozwiąż równanie 2^x = 20.
Rozwiązanie:
Logarytmujemy obie strony binarnie:
Odpowiedź: x = log₂ 20 ≈ 4.322
Częste błędy
Mylenie podstaw logarytmów
Uczniowie często mylą log₂ (podstawa 2), log (podstawa 10) i ln (podstawa e). To są różne funkcje dające różne wyniki. log₂ 8 = 3, log 8 ≈ 0.903, ln 8 ≈ 2.079.
Błąd: zakładanie, że log₂ 10 = 1. Poprawnie: log₂ 10 ≈ 3.322, natomiast log 10 = 1
Niewłaściwe upraszczanie log₂(2^x)
Wyrażenie log₂(2^x) zawsze upraszcza się do x, ponieważ logarytm binarny i potęgowanie o podstawie 2 znoszą się wzajemnie. Jest to tożsamość fundamentalna.
Błąd: pozostawienie log₂(2^x) w postaci niesprowadzonej. Poprawnie: log₂(2^x) = x
Zaokrąglanie w dół zamiast w górę
Przy obliczaniu liczby bitów potrzebnych do reprezentacji n wartości, wynik log₂ n należy zaokrąglić w GÓRĘ, nie w dół. Zaokrąglenie w dół daje za mało bitów.
Dla n=10: log₂ 10 ≈ 3.32. Potrzeba ⌈3.32⌉ = 4 bitów, nie 3 (bo 2³ = 8 < 10, ale 2⁴ = 16 ≥ 10)
Używanie log zamiast log₂ w informatyce
W analizie algorytmów i teorii informacji domyślnie używamy log₂, nie log₁₀. Gdy mówimy o złożoności O(log n), mamy na myśli log₂ n, choć podstawa nie zmienia klasy złożoności.
O(log₂ n) i O(log₁₀ n) to ta sama klasa złożoności, ale wartości liczbowe są różne
Porady i wskazówki
Zapamiętaj potęgi dwójki: 2¹ = 2, 2² = 4, 2³ = 8, 2⁴ = 16, 2⁵ = 32, 2⁶ = 64, 2⁷ = 128, 2⁸ = 256, 2⁹ = 512, 2¹⁰ = 1024. Ułatwia to szybkie obliczanie log₂.
Przeliczanie na inne podstawy: Większość kalkulatorów nie ma log₂, ale możesz użyć wzoru: log₂(x) = log(x)/log(2) ≈ log(x)/0.301 lub log₂(x) = ln(x)/ln(2) ≈ ln(x)/0.693.
Interpretacja w bitach: log₂ n (zaokrąglone w górę) to liczba bitów potrzebnych do zakodowania n różnych wartości. To kluczowa interpretacja w informatyce i teorii informacji.
W programowaniu: Wiele języków ma funkcję log2() w bibliotekach matematycznych. W C/C++: log2(x), w Python: math.log2(x), w JavaScript: Math.log2(x).
Przypadki szczególne
Logarytm binarny z 1
Logarytm binarny z 1 zawsze wynosi 0, ponieważ 2^0 = 1. Jest to szczególny przypadek ogólnego wzoru log_a 1 = 0.
To oznacza, że potrzeba 0 bitów do reprezentacji tylko jednej wartości
Logarytm binarny z 2
Logarytm binarny z podstawy 2 wynosi 1, zgodnie z ogólną zasadą, że log_a a = 1 dla dowolnej podstawy a.
Przykład: log₂ 2 = 1, log₂ 4 = 2, log₂ 8 = 3, log₂ 1024 = 10
Znoszenie się z wykładnikiem
Gdy logarytm binarny i funkcja wykładnicza o podstawie 2 są zastosowane do siebie nawzajem, znoszą się wzajemnie. To kluczowa właściwość funkcji odwrotnych.
Przykład: log₂(2⁷) = 7, 2^(log₂ 100) = 100
Liczby będące potęgami dwójki
Dla liczb będących potęgami dwójki logarytm binarny jest liczbą całkowitą równą wykładnikowi. To szczególnie przydatne w informatyce.
Przykład: 256 = 2⁸, więc log₂ 256 = 8 (bajt to 8 bitów)