时间复杂度和语句频度有什么区别?(数据结构问题)望高手指点!!谢谢!

2024-11-30 08:33:29
推荐回答(1个)
回答(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无关。也就是"忽略低阶"。