例2.1 算法如下：

  ①  x=0, y=0,

  ②  for(k=1;k<=n;k++)

  ③  x++;

  ④  for( i=1;i<=n;i++)

  ⑤  for(j=1;j<=n;j++)

  ⑥  y++；

  解 以上程序中频度最大的语句是⑥，其频度为 ，所以该程序时间复杂度是T(n)=O( ).

  当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度决定的。

  例2.2  算法如下：

  ①  x=1;

  ②  for( i=1; i<=n; i++)

  ③  for( j=1; j<=i; j++)

  ④  for(k=1;k<=j;k++)

  ⑤  x++;

  解 该程序段中频度最大的语句是⑤内的循环执行次数虽然与问题规模n没有直接关系，但是却与外层循环变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句⑤的执行次数:

 则该程序段的时间复杂度为T(n)=O( ).

2.2.2假设算法

    在某些循环结构的循环次数很难直接看出，特别是循环次数与某些循环体的语句k值，再计算出T(n),进而求T(n)的数量级.

例2.3 算法如下：

① i=s=0

② while(s<n)

③ i++；s=s+1;

解 执行到k次，i=k,s=0+1+2+3+……+k=  。该算法的时间复杂度T(n)=O( )。

2.2.3 递推算法

  当算法中包括递推函数时，其时间复杂度转化为一个递推关系。递推关系很多，介绍其中一种常见的，再根据递推关系一步步求出T(n)。

  例2.4 算法如下：源'自^751;文,论`文'网]www.751com.cn

  ① void sum(int a[],int n, int k)

  ② {int i；

  ③ if(k=n-1)

  ④ for(i=0;i<n;i++) printf(“%d”,a[i]);

  Else

  {For(i=k;i<n;i++) a[i]=a[i]+i;

  sum(a,n,k+1);}}

  解 设sun(a,n,k+1)执行时间为T(k),有算法的递归关系如下： 

  则T(0)=T(1)+n=T(2)+(n-1)+n=…=n+(n-1)+…+2+T(n-1)= = =O( )

所以，该算法的时间复杂度T(n)=O( ).

2.3 梅森素数

定义2.1 若 为素数（其中 为素数),则 称为梅森素数。

卢卡斯定理是梅森素数的重要判定定理——对于一个奇素数 ，梅森素数 为素数当且仅当 整除S(p-1),这里 且S(1)=4.

以下是我们用C语言实现的可实际使用的Lucas-Lehmer判定算法：

  {  Int S=4;

  Int i, S1;

  S1=2**p-1;

  For(i=3;i<=p;i++)。

  S=(S**2-2)%S1;  Return(S==0？1:0）  }

定义2.2 若O(n)=2n(O(n)为n的全体因数的和），则n称为完全数。