Начало: Математика для чайников. Глава 1. Что такое математическая абстракция.
Предыдущая глава: Математика для чайников. Глава 7. Множества
Есть в математике такая интересная операция – логарифм. Формально определение звучит так: «логарифмом числа b по основанию a называют степень, в которую нужно возвести основание a чтобы получить b ». Записывается это так:
Лучше всего это разъяснить на примере. Допустим, основание логарифма равно 2. Нужно вычислить логарифм числа 8. В какую степень нужно возвести 2, чтобы получить 8? Нетрудно догадаться, что в куб, то есть в третью степень. То есть:
Где можно использовать логарифмы? На самом деле, много где. Для решения показательных уравнений, в области компьютерной информации, в инженерном деле. Даже шкала измерения звука – она логарифмическая. Ну, и конечно же, логарифмы можно использовать для решения показательных уравнений, типа вот такого:
Решение этого уравнения было разобрано в главе Математика для чайников. Глава 5. Основы элементарной алгебры .
А теперь поговорим о том, как логарифмы можно использовать в области компьютерной информации. Для этого познакомимся немного с теорией алгоритмов. Как вы, наверное, поняли, теория алгоритмов – это наука, объектом исследования которой являться, алгоритмы. Но что в них моно исследовать? Ну, например, время выполнения алгоритмов. Одно и то же действие можно выполнить разными способами. Например, сложить все числа от 1 до 100 (или до миллиона, или до миллиарда). Можно просто тупо суммировать их (решить задачу в лоб). Компьютер работает быстро, и если чисел не так много, то решение задачи в лоб является самым легким и приемлемым решением, так как время выполнения будет меньше мгновения. Но что если надо сложить очень много чисел, и все они от 1 до какого-то очень большого числа? В этом случае и на компьютере расчет будет производиться долго. Как быть? Один из выходов – применить более оптимальный алгоритм. В случае с суммированием чисел можно просто воспользоваться формулой:
Таким образом, мы выполним операцию всего в три действия, каким бы большими не были числа.
- Но при чем тут логарифмы? - Спросите вы.
Минутку терпения. Сейчас мы рассмотрим алгоритм, время выполнения которого как раз и считается через логарифмы. Этот алгоритм – бинарный поиск. Такой поиск можно осуществить только в отсортированном массиве, и он работает гораздо быстрее, чем искать тупым перебором. Суть заключается вот в чем. Мы смотрим на середину массива, где надо произвести поиск. Если внезапно искомое значение оказалось равно значению в середине массива – то поиск закончили, нам повезло. А если нет? Это зависит от того, больше искомое значение тому, что в массиве или меньше. Если больше – значит, нам надо искать выше. Мы делим вторую половинку так же надвое и смотрим ее середину. Если меньше – то идем в серединку нижней половинки массива. И так до тех пор, пока не найдем число или пока мы больше не сможем делить половинки (в этом случае считаем, что число не нашли).
Для наглядности посмотрим схему этого поиска на картинке:
Так вот, время выполнения данного алгоритма пропорционально логарифму длины массива по основанию 2. То есть, если у нас в массиве 1024 элемента, то на поиск потребуется всего 10 шагов. А если миллион элементов – то всего 20 шагов. То есть, какой бы огромный не был массив, поиск в нем будет все равно очень быстрый.
Кстати, сама сортировка, если использовать оптимальный алгоритм сортировки, выполняется за время
Где n – количество элементов в массиве, a – основание логарифма (не меньше, чем 2), которое зависит от типа используемого алгоритма сортировки.
Посмотрим основные свойства логарифмов (основные логарифмические тождества):
Эти формулы пригодится при решении задач с логарифмами. Собственно, теперь решим задачу:
Найти корень уравнения
Используя формулу суммы логарифмов, преобразуем уравнение:
Откуда
Следующая глава: Математика для чайников. Глава 9. Основы матанализа