java - (c^k) 的大 O 表示法

Question

下面的代码给了我一个 O(n)。如何编写时间复杂度为 O(c^k) 的 for 循环？

int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2);
    else
        return x*power(x, y/2)*power(x, y/2);

}

Answer 1

不确定您要问什么，但是您可以清楚地修改此代码并通过简​​单地摆脱重复递归（而不是递归计算同一件事两次）来赢得很多。

if (y%2 == 0) {
    int res = power(x, y/2);    
    return res * res;
}

以这种方式编写它将允许您编写一个while循环而不是递归。

Answer 2

O(c^k)- 指数时间复杂度算法是，例如，蛮力搜索和旅行商问题。

我给你一个蛮力搜索的例子。如果你有一组长度的字符c，并且有长度的密码k。然后你需要O(c^k)时间来破解密码。