Question

请问数据结构的时间复杂度如何

请问数据结构的时间复杂度如何请问步骤是如何计算出来的执行次数

Answer 1

Answer 2

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无关。也就是"忽略低阶"。