python-3.x - Python 3 中 math.log2(x) 的时间复杂度是多少？

Question

正如标题所说，我想知道math.log2(x)的时间复杂度是多少.我知道可以用 O(1) 复杂度用 C 编写这样的函数，但是我找不到有关在 Python 中实现此函数的任何信息。

Answer 1

在 Python 的 CPython 实现中，log2 被实现为以下 C 函数，再加上一层在 C 中处理错误报告和特殊处理整数的层，但最终即使在整数情况下，也是下面的代码执行对数。

该逻辑基本上是使用标准的 C log2 函数(如果可用)，否则根据 log 计算 log2。在任何情况下，它都是 O(1)，但由于所有层的检查和 sanitizer ，它具有相对较高的常数因子。

/*
   log2: log to base 2.

   Uses an algorithm that should:

     (a) produce exact results for powers of 2, and
     (b) give a monotonic log2 (for positive finite floats),
         assuming that the system log is monotonic.
*/

static double
m_log2(double x)
{
    if (!Py_IS_FINITE(x)) {
        if (Py_IS_NAN(x))
            return x; /* log2(nan) = nan */
        else if (x > 0.0)
            return x; /* log2(+inf) = +inf */
        else {
            errno = EDOM;
            return Py_NAN; /* log2(-inf) = nan, invalid-operation */
        }
    }

    if (x > 0.0) {
#ifdef HAVE_LOG2
        return log2(x);
#else
        double m;
        int e;
        m = frexp(x, &e);
        /* We want log2(m * 2**e) == log(m) / log(2) + e.  Care is needed when
         * x is just greater than 1.0: in that case e is 1, log(m) is negative,
         * and we get significant cancellation error from the addition of
         * log(m) / log(2) to e.  The slight rewrite of the expression below
         * avoids this problem.
         */
        if (x >= 1.0) {
            return log(2.0 * m) / log(2.0) + (e - 1);
        }
        else {
            return log(m) / log(2.0) + e;
        }
#endif
    }
    else if (x == 0.0) {
        errno = EDOM;
        return -Py_HUGE_VAL; /* log2(0) = -inf, divide-by-zero */
    }
    else {
        errno = EDOM;
        return Py_NAN; /* log2(-inf) = nan, invalid-operation */
    }
}