Главная » Java, Структуры данных и алгоритмы » Краткий обзор математических понятий

0

В данном разделе проведен краткий обзор основных концепций дискретной математики, с которыми читатель встретится в различных частях книги. Кроме фундаментальных концепций, в приложении А представлен список полезных математических сведений, связанных с анализом структур данных и алгоритмов.

Логарифмическая и показательная функции

Одну из наиболее интересных и порой даже неожиданных возможностей анализа алгоритмов и структур данных представляет повсеместное использование логарифмических и показательных (экспоненциальных) функций, где

log^ а = с, а = ЬС.

В литературе компьютерной тематики принято уопускать основание логарифма Ь, если Ь = 2. Например, log 1024 = 10.

Существует ряд основных правил вычисления логарифмов и показательных функций. Ниже приводятся некоторые из них.

Утверждение 3.1. Пусть я, b и с — положительные действительные числа.

1.    log^ ас = log^ а + log^, с

2.                        Aogba  / c = logba-logbc

3.    log^ а° = c\o%b а

4.    \ogba=(\ogca)/\ogcb

5.    bXo%<a =a[ogcb

6.    (ba)c =bac

7.    babc =b™

8.    ba / bc =ba~c

Кроме того, используются формы записи log°п для обозначения (log п)с и log log п вместо log (log п). Вместо доказательства каждого из приведенных выше тождеств, которые вытекают из определение логарифмической и показательной функции, приведем несколько примеров их использования.

Пример 3.1. Ниже приводится несколько примеров, когда основание логарифма или показатель степени (экспонент) равен 2. В этих примерах используются правила, перечисленные в утверждении 3.1:

•                       2logn = n (по правилу 5),

•                       2llo&n = (2,0ё/,)2 = n2 (по правилам 5 и 6),

•                      4" =(22)n = 22" (по правилу 6),

•                       „2 23iog/» = n2 t пъ = ns правилам 5? 6 и 7),

•                      4" / 2" = 22n / 2" = 22n~« = 2" (по правилам 6 и 8).

Следует, однако, сделать одно замечание относительно использования логарифма. Дело в том, что значение логарифма, как правило, не является целым числом, в то время как время выполнения того или иного алгоритма выражается с помощью целочисленных значений, например, определяется количество выполненных операций. Таким образом, при проведении анализа иногда используются так называемые «минимальные» и «максимальные» функции, которые можно соответственно определить как:

LxJ = наибольшее целое число, меньшее или равное х,

Гх1 = наименьшее целое число, большее или равное х.

Данные функции позволяют преобразовывать значения реальных функций в целочисленные. Однако даже при наличии этих функций при анализе структур данных и алгоритмов зачастую используются реальные функции (например, п log п или пу2). Это означает, что в этом случае время выполнения алгоритма имеет «большую» максимальную функцию[9].

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии