algorithm - 计算该算法的时间复杂度

Question

我正在尝试计算此算法的时间复杂度，该算法确定正整数 N 是否可以表示为 x^y。该算法的作者是Vaibhav Gupta .

// Returns true if n can be written as x^y
bool isPower(unsigned int n)
{
    // Base case
    if (n <= 1) return true;

    // Try all numbers from 2 to sqrt(n) as base
    for (int x=2; x<=sqrt(n); x++)
    {
        unsigned  p = x;

        // Keep multiplying p with x while is smaller
        // than or equal to x
        while (p <= n)
        {
            p *= x;
            if (p == n)
                return true;
        }
    }
    return false;
}

作者说这个算法是第一个算法的优化版本:

// Returns true if n can be written as x^y
bool isPower(unsigned n)
{
    if (n==1)  return true;

    // Try all numbers from 2 to sqrt(n) as base
    for (int x=2; x<=sqrt(n); x++)
    {
        unsigned y = 2;
        unsigned p = pow(x, y);

        // Keep increasing y while power 'p' is smaller
        // than n. 
        while (p<=n && p>0)
        {
            if (p==n)
                return true;
            y++;
            p = pow(x, y);
         }
    }
    return false;
}

自从他使用 pow 函数以来，第一个是否具有不同的时间复杂度？

Answer 1

当它返回 false 时，算法会尝试增加所有整数 x 的幂，直到它们超过 n。尝试 x = √n 后搜索停止。

因此，对于粗略的评估，评估直到 x^d = n 的幂大约需要 log n/log x 的乘法，并且从 x= 2 到 x=√n。

因此复杂度就像

log n.Sum(x=2 to √n)1/log x

这不容易估计，但是 O(log n.√n) 和 Ω(√n)。

pow 版本采用 log d 乘法而不是 1 来计算幂，前提是它通过重复平方来计算。如d = log n/log x，复杂度为

log n.Sum(x=2 to √n)(log log n - log log x)/log x

更难估计，但是 O(log n.log log n.√n) 和 Ω(√n)。

对于int类型覆盖的n范围，你可以预期pow版本会慢一倍到五倍(除非pow 函数有很大的开销)。