Question

时间复杂度和语句频度有什么区别？（数据结构问题）望高手指点！！谢谢！

int sum1(int n){
int p=1,sum=0,i;
for(i=1;i<=n;i++){
p*=i;
sum+=p;
}
return(sum);
这道题怎么算时间复杂度和语句频度，要过程哦。。
请问下为什么可以是3n+3或3n+5？还有时间复杂度和语句频度区别在哪？时间复杂度是怎么算的？

Answer 1

1.频度计算:
int sum1(int n){
int p=1,sum=0,i; //频度：1(或3,总之是个常数与n无关)
for(i=1;i<=n;i++){ //频度：n+1
p*=i; //频度：n
sum+=p; //频度：n
}
return(sum); //频度：1
}
该函的执行频度为：3n+3（或3n+5)

2.时间复杂度计算
依据“频度”可知该函数为n的一次方，可表示为O(n)，也可表示为Θ(n)；后者更准确。
3.(补充)求“时间复杂度”是目的，“频度”仅是手段，前者要依据后者的计算。
4.(补充)求算法的“时间复杂度”是为了估计和比较不同算法处理同一问题时的效率，只“估计”即可，不必也不可能准确得出计算时间（涉及不同硬件、系统软件和编译系统等）
5.(补充)算法的时间复杂度计算问题涉及渐近符的使用，去看专门的算法分析书籍。其中有两个重要规则：忽略低阶，忽略系数。
6."3n+3"与"3n+5"问题，当n很大时，执行的时间与+3还是+5无关。也就是"忽略低阶"。