4

这是代码：

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)

如果我错了，请纠正我！

4

1 回答 1

1

O(sqrt n) 看起来很奇怪，但对我来说是正确的

于 2013-10-18T09:30:48.340 回答