python 3中math.log2（x）的时间复杂度是多少？

Question

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

谢谢！

Answer 1

[在Python C2的CPython实现中，log2被实现为以下C函数，在C之上的一层中处理错误报告并专门处理整数，但最终即使在整数情况下，它也是执行对数的以下代码。 >

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

/*
   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 */
    }
}