algorithm – 循环的运行时间直到i * i <= n

发布时间：2020-12-13 23:25:00 所属栏目：Linux 来源：网络整理

导读：这是代码： 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的命令吗？我的回答是

这是代码：

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 我< = sqrt(n) 如果我错了,请纠正我！

解决方法

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

algorithm – 循环的运行时间直到i * i &lt;= n

解决方法

algorithm – 循环的运行时间直到i * i <= n