代码如下:
int foo(int n)
{
if(n == 1)
return 1;
int f = 0;
int i;
for(i=1; i*i<=n; i++)
if(n%i == 0)
f+=2;
i--;
if(i*i == n)
f--;
return f;
}
我的问题是我无法为这个 for 循环确定 Θ，
我认为它是平方根(n)，但是否有一个名为平方根 n 的命令？
我的回答是:
Theta(sqrt(n)) 因为这个循环
for(i=1; i*i<=n; i++)
i * i <= n两边取 sqrt
i <= sqrt(n)
如果我错了请纠正我!
最佳答案
O(sqrt n) 看起来很奇怪，但对我来说是对的
关于algorithm - 一个循环的运行时间直到 i*i <= n，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19446149/