计算该算法的时间复杂度
计算该算法的时间复杂度
提问于 2016-04-08 20:31:01
我正在计算这个算法的时间复杂度，这个算法决定了一个正整数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函数？
回答 2
Stack Overflow用户
发布于 2016-04-08 21:22:39
当返回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函数有很大的开销)。
Stack Overflow用户
发布于 2016-04-08 20:38:38
在我看来，外部循环是n的平方根，内部循环的顺序是log n(因为数字呈指数级增长)，所以您的复杂度应该在
O(sqrt(n)*log n)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36499633
复制相关文章
相似问题
腾讯云开发者
