Логарифм

Определение

Логарифм — это математическая операция, обратная возведению в степень. Логарифм отвечает на вопрос: в какую степень нужно возвести одно число (основание), чтобы получить другое число.

Общая формула

${\log }_a(b)=c\text{ означает, что }{a}^c=b$

Где:

• $a$ — основание логарифма (должно быть > 0 и ≠ 1)
• $b$ — число, логарифм которого ищем (должно быть > 0)
• $c$ — искомый показатель степени

Основные виды логарифмов

Двоичный логарифм

• Обозначение: ${\log }_2(x)$
• Основание: 2
• Применение: информатика, теория алгоритмов

Пример: ${\log }_2(8)=3\text{, потому что }{2}^3=8$

Десятичный логарифм

• Обозначение: $\lg (x)$ или ${\log }_{10}(x)$
• Основание: 10
• Применение: инженерные расчеты

Пример: $\lg (100)=2\text{, потому что }10^2=100$

Натуральный логарифм

• Обозначение: $\ln (x)$
• Основание: $e\approx 2.718$ (число Эйлера)
• Применение: математика, машинное обучение

Пример: $\ln (e^3)=3\text{, потому что }{e}^3=e^3$

Примеры вычисления

Простые примеры

1. ${\log }_2(16)=4$ → потому что $2^4=16$
2. ${\log }_2(32)=5$ → потому что $2^5=32$
3. ${\log }_{10}(1000)=3$ → потому что $10^3=1000$
4. ${\log }_3(9)=2$ → потому что $3^2=9$
5. ${\log }_5(125)=3$ → потому что $5^3=125$

Важные свойства

Свойство	Формула	Пример
Логарифм единицы	${\log }_a(1)=0$	${\log }_2(1)=0$
Логарифм основания	${\log }_a(a)=1$	${\log }_5(5)=1$
Логарифм произведения	${\log }_a(xy)={\log }_a(x)+{\log }_a(y)$	${\log }_2(8\cdot 4)=3+2=5$
Логарифм частного	${\log }_a(x/y)={\log }_a(x)-{\log }_a(y)$	${\log }_2(16/4)=4-2=2$
Логарифм степени	${\log }_a(x^n)=n\cdot {\log }_a(x)$	${\log }_2(8^2)=2\cdot 3=6$

Применение в программировании

Сложность алгоритмов

Двоичный логарифм показывает, сколько раз нужно делить число пополам, чтобы получить 1:

• ${\log }_2(1000)\approx 10$ → массив из 1000 элементов можно разделить пополам ~10 раз
• ${\log }_2(1000000)\approx 20$ → массив из миллиона элементов — ~20 раз

Примеры сложностей

Сложность	Описание	Пример алгоритма
$O(\log n)$	Логарифмическая	Бинарный поиск
$O(n\log n)$	Линейно-логарифмическая	Быстрая сортировка, сортировка слиянием
$O(n^2)$	Квадратичная	Пузырьковая сортировка

Практический пример

// Бинарный поиск имеет сложность O(log n)
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}
 
// Для массива из 1000 элементов потребуется максимум log₂(1000) ≈ 10 итераций