algorithm - 以下算法的运行时(来自破解编码面试的示例)

Question

破解编码面试书的问题之一是询问以下算法的运行时，该算法打印从 1 到 n 的 2 的幂:

int powersOf2(int n) {
    if (n < 1) return 0;
    else if (n == 1) print(1); return 1;
    else
    {
        int prev = powersOf2(n/2);
        int curr = prev * 2;
        print(curr); 
        return curr;
    }
}

作者回答说它在 O(log n) 中运行。

这很有道理，但是... n 是输入的值! (伪次线性 运行时)。

说运行时间是 O(m) 是不是更正确，其中 m 是算法的输入长度？ (O(log(2^m)) = O(m))。

或者简单地说它在 O(log n) 中运行而不提及任何关于伪运行时的事情是否完全没问题...

我正在准备面试，想知道是否需要提及运行时是伪次线性，以解决此类依赖于输入值的问题。

Answer 1

我认为您在这里寻找的术语是“weakly polynomial”，意思是“输入位数的多项式，但仍取决于输入的数值。”

这是您需要在面试中提及的内容吗？可能不会。分析算法并说运行时间为 O(log n) 将运行时间完美地描述为输入参数 n 的函数。更进一步，然后查看写出数字 n 需要多少位，然后提到运行时与输入的大小成线性关系，这是一个很好的繁荣，可能会让面试官高兴。

如果你不提这个，如果面试官对你不利，我真的会很不高兴 - 这是你只有接受过良好的大学教育或进行了大量自学才能知道的事情.