Question

分析以下算法的时间复杂度，最好能告诉我怎么算，多谢了

题目如下：
int INTI(int n)
{for(i=2;i<sqrt(n);i++)
if(n%i==0)
return 0;
return 1;
}

long sun(int n)
{s=0;
for(i=1;i<=n;i++
for(i=1,j=1;j<i;j++)
p=p*j;
s+=p;
}
return s;
}

Answer 1

你上下好像是两个独立的函数，那就分开算：

第一个计算从2到n的平方根，有没有n的因子，有返回0，没有返回1，应该是一个判断n是否是质数的函数，那么它的复杂度是动态的，最好的可能是能被2除，则复杂度为1，最差的情况是n是质数，则复杂度为n的平方根-1，可以简单记为O(n的开方)

第二个，可能有些语法错误：

1. p是什么，全局变量？因为涉及p*j所以p的初值很关键

2. 第二个for循环把i重置为1和j相同，所以导致此for循环不会执行，那么整体的复杂度就是第一重循环即O(n)

如果做如下改动：

long sun(int n)
{ 
    int s = 0, p = 0;
  
    for(i = 1; i <= n; i++) 
    {
        p = 1; 
        for(j = 1; j <= i; j++)
            p = p * j;

        s += p;
    }
  
    return s;
}

 那这个程序就变成了求1到n所有数的阶乘的和，那么它的复杂度为：

1. 一重for循环，执行了n次

2. 二重for循环，执行的次数相当于一个从1到n的等差数列的和，为(n+1)*n/2，即n^2/2 + n/2

当n趋近无穷时，可以忽略低次幂和系数，即其复杂度为O(n^2)

Answer 2

O(n^0.5)
如果第2题中for(i=1,j=1...)是正确的，那就O(n)，如果去掉i=1则是O(n^2)

Answer 3

第一个是o（n）
第二个是o（n*n）

追问

我个人觉得第二个的时间复杂度为O(n)因为它的循环次数为1+2+3+4+...+n=(n+1)/2.不考虑常数项和系数为n