Какова сложность логарифмической функции?

Это действительно зависит от области значений, для которых вы хотите вычислить логарифм.

Для дублей IEEE многие процессоры могут логарифмировать в одной ассемблерной инструкции; Например, в x86 есть инструкции FYL2X и FYL2XP1. Хотя обычно подобные инструкции принимают логарифмы только по некоторому фиксированному основанию, их можно использовать для логарифмирования по произвольным основаниям, используя тот факт, что

log_a b = log_c b / log_c a

просто взяв два логарифма и найдя их частное.

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

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

Надеюсь это поможет!

Чтобы сделать log(n) в O(1) (где n — целое число)

int log(long long x)
{
    return 64 - __builtin_clzl(x) - 1;
}

__builtin_clzl(x) см. здесь