Описание тега logarithm

Описание тега Вопросы с тегом
Логарифм числа - это показатель степени, на который нужно поднять другое фиксированное значение, основание, чтобы получить это число. Он имеет приложения в алгебре и теории сложности. Обычно в языках программирования обозначается как log. Используйте этот тег для любых вопросов программирования, связанных с логарифмами.

Логарифм числа по основанию b представляет показатель степени, до которого необходимо возвести b, чтобы получить исходное число. А именно, для числа n это все равно, что задать вопрос: " Какая степень b равна n?"

Учитывая число n

  • Выразите n = b x для некоторой базы b и некоторой степени x.
  • Тогда логарифм числа n по основанию b является показателем x. журнал б (п) = х.

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

Обозначения логарифма числа n для разных оснований:

  • log b(n) для данной базы b
  • log(n), что может означать десятичный логарифм, натуральный логарифм или общий логарифм
  • ln(n), который часто, но не всегда используется для натурального логарифма.

Кроме того, основание логарифма можно изменить с помощью простой формулы, включающей соотношение логарифмов. Фактически, логарифм основания c выражается как постоянное кратное логарифму основания b.

  • журнал c(n) = журнал b(n) / журнал b(c)

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

Логарифм в языках программирования

В отличие от простых аддитивных и мультипликативных операторов, а в некоторых случаях показатель степени, использующий логарифм для данного языка программирования, обычно используется как особый метод встроенной библиотеки. Логарифм обычно принимает входные данные с плавающей запятой строго больше нуля и возвращает приблизительный логарифм числа, обычно натуральный логарифм.

Кроме того, обратите внимание, что имя log(...) часто относится к натуральному логарифму в контексте языков программирования, а не к ln(...). Журнал с основанием 10 обычно называетсяlog10(...).

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

Использование в различных языках программирования (base-e)

  • C / C++: log(double x) (импорт <math.h> обязательный)
  • Джава: Math.log(double x)
  • JS: Math.log(x) (не путайте с console.log)
  • Python: log(x), log(x, b)для логарифма с основанием b (требуется импорт изmath модуль)
  • Фортран: LOG(x)
  • MySQL: LOG(x), LOG(b, x)для логарифма по основанию b числа x
  • Excel: LN(x), LOG(x, b)для базы- b

Применение логарифмов

Логарифм является обратной величиной возведения в степень, а именно: log b (b n), b log b(n) - это тождества, которые равны исходному числу n.

Логарифмы важны во многих математических областях, особенно в тех, которые включают переменные, различающиеся на много порядков, логарифмические оси и решения формул, включающих экспоненциальные выражения. Это также способ интерполировать количество цифр (некоторой базы b) данного числа: количество десятичных цифр, необходимых для положительного целого числа n, равно ⌊log10(n)⌋.

Логарифм также представляет собой главный класс сложности в теории алгоритмической сложности. Логарифмическая сложность представляет собой временную или пространственную сложностьO(log(n))для входа размера n. Логарифмический рост происходит очень медленно и асимптотически медленнее, чем любая степенная функция n c, где c строго положительно, включая линейную функцию. Следовательно, логарифмическая сложность очень эффективна и считается полиномиальным временем.

Все эти алгоритмы являются логарифмическими по времени:

  • Бинарный поиск
  • BST Insertion (средний случай)

Существует также другой основной класс сложности, называемый линейной сложностью, который представляетO(n * log(n))сложность. Обычно это происходит, когда процесс логарифмической сложности выполняется n раз. Это асимптотически медленнее, чем любая степенная функция n c, где c > 1.

Все эти алгоритмы работают в линейном режиме или n-log-n времени.

  • Быстрая сортировка (средний случай)
  • Перечисление всех элементов в BST (средний случай)

Подробнее

Документация

Теги

  • log: НЕ используйте этот тег для логарифмов. Слово "журнал" также используется для обозначения действия записи в журнал. Этот тег предназначен только для логарифмов и логарифмических понятий.
  • ln: НЕ используйте этот тег для натурального логарифма. Это относится к команде ссылки. Вместо этого используйте натуральный логарифм.
  • возведение в степень, pow: Обратные значения логарифма
  • exp: относится к натуральной экспоненте, обратнойlog(...).
    А именно,log(exp(x)) == exp(log(x)) == x за x > 0.
  • сложность, временная сложность, пространственная сложность, асимптотическая сложность: логарифм - важный класс алгоритмической сложности. Он очень эффективен, намного эффективнее линейного, но меньше постоянного.

внешняя ссылка